题目描述

给出一个长度为 $N$ 的序列 $A$ ，要求维护以下两种操作

1 l r f 将区间 $[l, r]$ 内的元素按照升序 $(f = 1)$ 或降序 $(f = 0)$ 排序

2 l r 询问 $[l, r]$ 内的元素的积的十进制的最高位

输入格式

第一行两个正整数 $N, M$。

接下来一行 $N$ 个正整数 $A_i$。

接下来 $M$ 行每行一个操作。

输出格式

对于每个询问输出一行

样例

input

10 11
1 5 10 3 9 2 8 6 4 7
2 5 8
1 1 3 0
2 2 6
1 6 8 1
2 1 10
2 4 9
1 2 5 0
1 4 8 1
1 3 6 0
2 1 10
2 3 8

output

8
2
3
1
3
1

数据范围与提示

对于 $20\%$ 的数据，没有操作 $1$；

对于另 $20\%$ 的数据，$N, M\leq 1000$ 且区间乘积在 $64$ 位整数范围内；

对于另 $20\%$ 的数据，$N, M\leq 1000$；

对于所有数据，$N, M\leq 200000, 1\leq A_i\leq N$。