택 뭉 볃교

정수 $n$에 대한 함수 $f(n)$은 다음과 같이 정의된다.

즉, 위 함수는 정수 $n$을 이진수로 나타내었을 때 1의 개수를 $n$에 대한 함숫값으로 한다.

길이가 $N$인 수열 $A_1, A_2, \cdots, A_N$과 $B_1, B_2, ..., B_N$이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하라.

• 1 l r x : $l \le i \le r$인 $i$에 대해 $A_i := A_i \oplus x$를 수행한다.
• 2 l r x k : $l \le i \le r$인 $i$에 대해 $B_i := B_i + k \times f(A_i \oplus x)$를 수행한다.
• 3 l r : $\sum_{l \le i \le r} B_i$을 출력한다.

첫 번째 줄에 수열의 크기 $N$이 주어진다.

두 번째 줄에는 $A_1, A_2, ..., A_N$이 주어진다.

세 번째 줄에는 $B_1, B_2, ..., B_N$이 주어진다.

네 번째 줄에는 쿼리의 개수 $Q$가 주어진다.

다섯 번째 줄부터 $Q$개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

3번 쿼리가 주어질 때마다 정답을 줄 바꿈으로 구분하여 출력한다.

• $1 \le N, Q \le 10^5$
• $0 \le A_1,\ A_2,\ \cdots,\ A_N < 2^{20}$
• $-10^6 \le B_1,\ B_2,\ \cdots,\ B_N \le 10^6$
• $1$번 쿼리에서 $1\ \le l \le r \le\ N;\ 0\ \le x <\ 2^{20}$
• $2$번 쿼리에서 $1 \le l \le r \le N;\ 0 \le x < 2^{20};\ -10^6 \le k \le 10^6$
• $3$번 쿼리에서 $1 \le l \le r \le N$