산술 수업

와칸다의 한 평범한 학교에서 오늘 산술 수업으로 정수의 비트 연산을 배웁니다.

대상 연산은 and와 xor입니다. 비트 연산은 두 수의 각 비트에 대해 독립적으로 수행됩니다. 진리표는 다음과 같습니다.

수업 시작에 선생님이 길이 $n$인 수열을 칠판에 적습니다. 선생님은 학생들에게 다음 연산을 차례로 수행하라고 합니다.

• 선생님이 수 $x$를 말합니다. 학생들은 현재 수열의 모든 원소에 xor $x$를 적용해 새 수열을 만듭니다.
• 선생님이 수 $x$를 말합니다. 학생들은 현재 수열의 모든 원소에 and $x$를 적용해 새 수열을 만듭니다.
• 선생님이 수 $l$과 $r$을 말합니다. 학생들은 현재 수열에서 $l$ 이상 $r$ 이하인 원소의 개수를 답합니다.

학생들이 선생님의 모든 질문에 올바르게 답하도록 도와주세요.

첫 줄에 수열의 길이 $n$과 수행할 연산의 개수 $q$가 주어집니다 ($1 \le n \le 100\,000$, $0 \le q \le 100\,000$). 둘째 줄에는 초기 수열의 원소 $a_i$가 $n$개 주어집니다 ($0 \le a_i < 2^{20}$). 이후 $q$개 줄에 연산이 한 줄씩 주어집니다.

줄이 xor로 시작하면 첫 번째 유형입니다. 같은 줄에 수 $x$($0 \le x < 2^{20}$)가 주어지고, 현재 수열의 모든 원소 $cur_i$를 $cur_i$ xor $x$ 값으로 바꿉니다.

줄이 and로 시작하면 두 번째 유형입니다. 같은 줄에 수 $x$($0 \le x < 2^{20}$)가 주어지고, 모든 원소 $cur_i$를 $cur_i$ and $x$ 값으로 바꿉니다.

줄이 ?로 시작하면 세 번째 유형입니다. 같은 줄에 정수 $l$과 $r$($0 \le l \le r < 2^{20}$)이 주어지고, $l \le cur_i \le r$을 만족하는 현재 수열의 원소 $cur_i$의 개수를 구합니다.

세 번째 유형의 각 연산에 대해 답을 새 줄에 출력합니다.

첫 번째 테스트에 대한 설명입니다.

xor 1 연산 후 수열은 $0$, $3$, $2$, $5$, $4$가 됩니다.

and 2 연산 후 수열은 $0$, $2$, $2$, $0$, $0$이 됩니다.