수열 생성

길이가 $n$인 수열 $a_1, a_2, \\ldots, a_n$이 있으며, 모든 $a_i$는 홀수임이 보장된다.

연산은 두 종류이다.

1. $\\ell$, $r$, $x$가 주어지면, a_\\ell, a_{\\ell + 1}, \\ldots, a_r 각각에 짝수 $x$를 더한다.
2. $\\ell$, $r$이 주어지면, a_\\ell, a_{\\ell + 1}, \\ldots, a_r의 곱을 구하고 그 값을 $2^{20}$으로 나눈 나머지를 출력한다.

초기 수열과 연산이 주어졌을 때, 이를 효율적으로 처리하라.

첫째 줄에 두 양의 정수 $n$, $q$ ($1 \\leq n, q \\leq 2 \\cdot 10^5$)가 주어진다. 각각 수열의 길이와 질의의 개수이다.

둘째 줄에는 홀수 $a_1, a_2, \\ldots, a_n$ ($1 \\leq a_i < 2^{20}$)이 $n$개 주어진다.

이후 $q$개의 줄에는 다음 두 형식 중 하나의 질의가 주어진다.

• 1 l r x: 첫 번째 연산을 수행한다 ($1 \\leq \\ell \\leq r \\leq n$, $x$는 짝수이고 $0 \\leq x < 2^{20}$).
• 2 l r: 두 번째 연산을 수행한다 ($1 \\leq \\ell \\leq r \\leq n$).

질의에 주어지는 값은 모두 정수이다.

두 번째 형식의 질의마다 답을 한 줄에 출력한다.