题目描述

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

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

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

输入格式

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

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

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

输出格式

对于每个询问输出一行表示答案。

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

8
2
3
1
3
1

数据范围与提示

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

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

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

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