물리 실험 수행 5분전

경기과학고 우정 1관에 존재하는 사물함의 비밀번호는 $N$개의 $0$ 이상 $M$이하의 정수로 이루어진 수열 $A = \{a_1, a_2, \dots, a_N\}$이다. 이 사물함은 매우 특별한 능력을 갖고 있는데, 사물함을 오래 닫아놓고 있으면 비밀번호가 저절로 바뀐다! 이 때문에 대부분의 경기과학고 학생들은 사물함 문을 닫아놓고 다시 열지 못하는 불상사를 자주 겪는다. 다행히도 학교 선생님들께서는 마스터 키를 가지고 계셔서 사물함을 영원히 열지 못하는 일은 발생하지 않는다.

영민이는 현재 극심한 공포를 느끼고 있다. 다음 교시가 물리 실험 수행이지만 실험복을 넣어둔 사물함이 열리지 않는다! $(M+1)^N$ 개의 비밀번호를 모두 시도 해볼 여유가 없는 영민이는 자신이 존경하는 경기과학고등학교 수학 선생님께 도움을 청하고자 한다. 하지만 학교 일로 바쁘셨던 선생님께서는 현재 마스터 키를 주러 오실 수 없는 상황이다. 대신 비밀번호에 대한 힌트만 주시기로 하였다. 힌트는 비밀번호의 특정 두 자리의 합과 차에 대한 정보이고, 영민이가 똑똑하다는 것을 아시는 선생님께서는 가끔씩 이전 힌트들과는 모순된 힌트를 주시기도 한다.

또한 선생님께서는 영민이가 거짓 힌트에 속지 않고 잘 따라오고 있는지 확인하기 위해, 중간중간 돌발 질문을 던지신다. 이때 영민이는 사전 순으로 가장 앞서는 수열을 기준으로 대답해야 한다.

영민이를 도와 다음 쿼리들을 처리하는 프로그램을 작성해 주자.

$\cdot\space\space 1\space i\space j\space z\space:$ 선생님께서 $a_i + a_j = z$ 라는 힌트를 주신다. 이전에 적용한 힌트들과 모순이 되지 않는 경우 적용한다.

$\cdot\space\space 2\space i\space j\space z\space:$ 선생님께서 $a_i - a_j = z$ 라는 힌트를 주신다. 이전에 적용한 힌트들과 모순이 되지 않는 경우 적용한다.

$\cdot\space\space 3\space i\space j\space :$ 선생님의 돌발 질문이다. 지금까지 적용한 힌트들을 모두 만족하는 수열 $A$ 중, 사전 순으로 가장 앞서는 수열 $A'$에 대해 $a_i + \cdots + a_j$ 를 출력해야한다.

1번과 2번 쿼리의 경우, 이전에 적용한 힌트들이나 수의 범위 조건($0 \le a_k \le M$)과 모순을 일으킨다면, 선생님의 장난으로 간주하여 무시하고 0을 출력한다. 모순이 없다면 힌트를 적용하고 1을 출력한다.

첫째 줄에 수열의 길이 $N$, 원소의 최댓값 $M$, 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. ($2 \le N \le 2\times 10^5$, $1 \le Q \le 2\times 10^5$, $0 \le M \le 10^9$)

둘째 줄부터 $Q$개의 줄에 걸쳐 쿼리의 정보가 주어진다. 각 줄의 첫 번째 정수는 쿼리의 종류를 나타낸다.

$\cdot\space\space1\space i\space j\space z\space:$ ($1 \le i, j \le N$, $i \neq j$, $0 \le z \le 2M$)

$\cdot\space\space2\space i\space j\space z\space:$ ($1 \le i, j \le N$, $i \neq j$, $-M \le z \le M$)

$\cdot\space\space3\space i\space j\space:$ ($1 \le i \le j \le N$)

1번, 2번 쿼리에 대해 힌트가 모순 없이 적용되었다면 1, 모순이 발생하여 무시되었다면 0을 한 줄에 하나씩 출력한다.

3번 쿼리에 대해 조건을 만족하는 사전 순으로 가장 앞서는 수열의 구간 합을 한 줄에 하나씩 출력한다.

$\cdot\space$SubTask 1 : 1번 쿼리에 대해 $z = 0$ 또는 $z = 2M$ 이고 2번 쿼리에 대해 $z = -M$ 또는 $z = M$ 이다. (15)

$\cdot\space$SubTask 2 : $Q \le 10^3$ (15)

$\cdot\space$SubTask 3 : $N \le 10^5,\space Q \le 5\times 10^4$ (55)

$\cdot\space$SubTask 4 : $Q \le 2\times 10^5$ (15)