시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB177538.462%

문제

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

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

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

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

  • $1\space i\space j\space z\space:$ 선생님께서 $a_i + a_j = z$ 라는 힌트를 주신다. 이전에 적용한 힌트들과 모순되지 않는 경우 적용한다.
  • $2\space i\space j\space z\space:$ 선생님께서 $a_i - a_j = z$ 라는 힌트를 주신다. 이전에 적용한 힌트들과 모순되지 않는 경우 적용한다.
  • $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$가 공백으로 구분되어 주어진다.

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

출력

각 쿼리에 대해 답을 한 줄에 하나씩 출력한다.

제한

  • $2 \le N \le 2\times 10^5$
  • $0 \le M \le 10^9$
  • $1 \le Q \le 2\times 10^5$
  • $1$번 쿼리에서 $1 \le i, j \le N$, $i \neq j$, $0 \le z \le 2M$
  • $2$번 쿼리에서 $1 \le i, j \le N$, $i \neq j$, $-M \le z \le M$
  • $3$번 쿼리에서 $1 \le i \le j \le N$
  • 주어지는 모든 수는 정수

서브태스크

번호배점제한
15

$1$번 쿼리에 대해 $z = 0$ 또는 $z = 2M$ 이고 2번 쿼리에 대해 $z = -M$ 또는 $z = M$

215

$Q \le 10^3$

310

$2$번 쿼리만 주어짐

415

$1, 2$번 쿼리만 주어짐

540

$2, 3$번 쿼리만 주어짐

615

추가 제약 조건 없음

예제 입력 1

5 10 5
2 1 2 2
3 1 2
2 2 3 2
3 1 3
3 4 5

예제 출력 1

1
2
1
6
0

예제 입력 2

10 100 5
1 1 2 10
1 3 4 10
2 2 3 0
3 1 4
3 1 10

예제 출력 2

1
1
1
20
20

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.