考虑一个包含 $N$ 个整数的序列 $a_i$。 允许进行两种类型的操作：

• 将下标从 $L$ 到 $R$（包含 $L$ 和 $R$）范围内的所有序列元素设置为值 $x$。
• 查找序列中从下标 $L$ 到 $R$（包含 $L$ 和 $R$）这一部分的支配元素。

如果序列中超过一半的元素等于 $b$，则称元素 $b$ 为该序列的支配元素。 给定初始序列，执行这些操作并输出结果。

输入格式

输入的第一行包含序列中元素的数量 $N$ ($1 \le N \le 200\,000$)。第二行包含 $N$ 个值 $a_i$ ($0 \le a_i < 10^6$)。第三行包含操作的数量 $Q$ ($1 \le Q \le 200\,000$)。接下来的 $Q$ 行中，每行描述一个操作。第一类操作格式为 “set $L$ $R$ $x$”，其中 $1 \le L \le R \le N$ 且 $0 \le x < 10^6$。第二类操作描述为 “query $L$ $R$”，其中 $1 \le L \le R \le N$。所有数字均为整数。

输出格式

对于每个第二类操作，输出一行包含支配元素的值（如果存在），如果不存在，则输出 $-1$。

样例

输入 1

10
1 2 1 2 1 2 1 2 1 2
10
query 1 10
query 2 10
query 1 9
set 1 5 3
query 2 3
query 1 10
query 1 9
set 1 10 1
query 2 3
query 1 10

输出 1

-1
2
1
3
-1
3
1
1