UOI 虽然非常高级，在赛时就可以得到成绩。但是在比赛结束的一刹那，一条外星亖手蚯蚓钻进了存储着比赛成绩的机器里，随即机器开始冒烟。

外星亖手蚯蚓立刻被众人控制住了，勒令将比赛成绩从该机器的数据盘里恢复出来。可是亖手蚯蚓脑回路比较奇怪，所以恢复数据的方式也非常的怪。

在一开始，数据盘里面存储着一个整数序列 $a$。然后每一步，亖手蚯蚓会先给定一个区间 $[l,r](1\le l\le r\le n)$。然后进行以下三种操作之一：

• $1lrv$: 给定 $v$, 对于 $l\le i\le r$，将 $a_i$ 变为 $\lfloor \frac{a_i}{v}\rfloor$。这里我们保证 $v\ge 1$。

• $2lrv$: 给定 $v$, 对于 $l\le i\le r$，将 $a_i$ 变为 $a_i\mathrm{\&}v$，其中 $\mathrm{\&}$ 是按位与运算。

• $3lr$: 向你询问 $a_i$（$l\le i\le r$）的总和。

虽然你不太理解亖手蚯蚓这通诡异的操作，但你还是乖乖地回答着亖手蚯蚓的一个个询问。不过有没有可能做得快一点呢？

输入格式

第一行两个正整数 $n,q$，表示序列 $a$ 的长度和询问个数。

下面一行 $n$ 个整数 $a_i$，以 $16$ 进制读入。

下面 $q$ 行，每行第一个正整数 $o{p}_i$ 表示操作编号。

对于 $o{p}_i=1$ 或 $o{p}_i=2$，后面紧跟三个整数 $l_i,r_i,v_i$，表示执行上述对应操作, 其中 $v_i$ 以 $16$ 进制读入。

对于 $o{p}_i=3$，后面紧跟两个整数 $l_i,r_i$，表示询问这个区间的元素的和对 $2^{128}$ 取模的值，以 $16$ 进制输出。

在本题中所有的十六进制数 仅包含字符 0 $\sim$ 9,a $\sim$ f，分别代表着 $0\sim 9,10\sim 15$，同时 不存在无效前导零 。本题的所有 $16$ 进制输入保证满足如上格式，选手的输出也需要满足如上格式。

提示: UOJ 中可以使用 $128$ 位无符号整型数字 __uint128_t，但需要手动实现 IO，我们提供了 IO 模板在题面结尾。

输出格式

若干行，对于每个询问，输出其答案。

样例一

input

5 5
1 9 1 9 1
3 2 3
2 1 3 5
3 1 5
1 1 5 3
3 1 5

output

a
d
3

样例二

见附加文件中 ex_machine2.in 与 ex_machine2.out。

样例三

见附加文件中 ex_machine3.in 与 ex_machine3.out，其中所有数不超过 $2^{40}$。

限制与约定

对于 $100\mathrm{\%}$ 的数据，$1\le l_i\le r_i\le n\le 300000,1\le q\le 200000,0\le v_i,a_i<2^{128}$，其中操作一的 $v_i\ge 1$。

时间限制：$\mathtt{\text{3s}}$

空间限制：$\mathtt{\text{1GB}}$

提示

提示：请注意你的算法的时间复杂度。

提示: UOJ 中可以使用 $128$ 位无符号整型数字 __uint128_t，但需要手动实现 IO，我们在下方提供了模板。

typedef __uint128_t u128;
inline u128 read() {
    static char buf[100];
    scanf("%s", buf);
    // std::cin >> buf;
    u128 res = 0;
    for(int i = 0;buf[i];++i) {
        res = res << 4 | (buf[i] <= '9' ? buf[i] - '0' : buf[i] - 'a' + 10);
    }
    return res;
}
inline void output(u128 res) {
    if(res >= 16)
        output(res / 16);
    putchar(res % 16 >= 10 ? 'a' + res % 16 - 10 : '0' + res % 16);
    //std::cout.put(res % 16 >= 10 ? 'a' + res % 16 - 10 : '0' + res % 16);
}