问题描述

一个学校由编号为1到N的N个学生组成，进行了期末考试。考试满分100分，每个学生获得非负整数的分数。

在这个学校里，每个学生都会被通知自己的得分以及所有参加考试的学生的总分，但除此之外的信息不会被通知。

然而，每个学生都对其他学生的得分感到好奇。因此，学生通过询问其他学生的得分，基于这些值来预测其他学生的得分。

作为学校的教师，您对学生们能够准确了解其他学生的得分有多感兴趣，于是决定调查学生的行为究竟能够确定多少分。

具体而言，在处理按升序排序的M个信息查询或问题查询时，将计算问题查询的答案。

• 查询被分配从1到M的编号。每个查询由三个整数ai（0≦ai≦1），bi（1≦bi≦N）和ci（1≦ci≦N，bi≠ci）确定。
• 当ai = 0时，查询i是一个信息查询。这表示学生bi知道学生ci的得分。
• 当ai = 1时，查询i是一个问题查询。这表明学生bi必须回答学生ci的得分至少是多少分和最多是多少分，只能基于查询i之前的信息查询和已知信息来回答。

输入

输入以以下格式从标准输入给出。

N s1 s2 : sN M a1 b1 c1 a2 b2 c2 : aM bM cM

• 第一行给出学校的学生人数N（2 ≤ N ≤ 50）。
• 第二行到第N行给出学生的得分。其中第i行（1 ≤ i ≤ N）给出学生i获得的得分si（0 ≤ si ≤ 100）。
• 第N + 2行给出查询数量M（1 ≤ M ≤ 5,000）。
• 第N + 3行到第N + M + 2行给出查询的信息。其中第i行（1 ≤ i ≤ M）以空格分隔给出三个整数ai（0 ≤ ai ≤ 1），bi（1 ≤ bi ≤ N）和ci（1 ≤ ci ≤ N，bi≠ci）。
• 对于整数i（1 ≤ i ＜ j ≤ M），如果ai = aj = 0，则必须成立bi ≠ bj或ci ≠ cj。
• 输入确保至少有一个整数i满足ai = 1（即至少有一个问题查询）。

输出

输出包括Q行，其中Q是问题查询的数量。其中第i行（1 ≤ i ≤ Q）输出第i个问题查询的答案。如果第i个问题查询的答案是得分不低于x分且不高于y分，则按照这个顺序输出x和y，以空格分隔。输出末尾包含换行符。

输入样例1

4
80
90
70
100
6
0 2 3
0 4 2
1 2 4
0 2 4
1 2 1
1 4 1

输出样例1

80 100
80 80
50 100

学校共有4名学生，共有6个查询。

• 查询1是一个信息查询。学生2了解到学生3的得分是70分。
• 查询2是一个信息查询。学生4了解到学生2的得分是90分。
• 查询3是一个问题查询。在此时，学生2已经知道总分是340分（即80+90+70+100=340），学生2的得分是90分，学生3的得分是70分，所以我们可以得出结论：学生4的得分在80到100之间。因此，第1行的输出是80 100。
• 查询4是一个信息查询。学生2了解到学生4的得分是100分。
• 查询5是一个问题查询。在此时，学生2已经知道所有学生的总分（除了学生1）和除了学生1的其他所有学生的得分，因此学生1的得分正好是80分。因此，第2行的输出是80 80。
• 查询6是一个问题查询。在此时，学生4已经知道总分是340分，学生2的得分是90分，学生4的得分是100分，因此我们可以得出结论：学生1的得分在50到100之间。因此，第3行的输出是50 100。

输入样例2

3
25
12
31
3
1 1 2
0 1 2
1 1 2

输出样例2

0 43
12 12

查询也可能针对已经知道分数的学生。

输入样例3

7
32
19
22
25
23
17
18
11
0 1 2
0 4 5
0 1 4
0 2 3
0 2 7
1 1 5
1 2 7
1 2 1
0 4 3
1 4 2
1 6 7

输出样例3

0 80
18 18
0 97
0 86
0 100