M - 秘密の数列と分岐するノート 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

高橋君と青木君は、N 個の隠された整数 A_1, A_2, \ldots, A_N を推理しています。

各 A_i は 0 以上 K - 1 以下の整数ですが、具体的な値は二人には分かっていません。

区間 [L, R] のスコアを、次の値として定義します。

(A_L + A_{L+1} + \cdots + A_R) \bmod K

二人は、推理の記録をノートの「版」として管理しています。

各操作は既存の版を参照して行われ、その結果として新しい版が作られます。これにより、版は木状に分岐していきます。

最初に、受理された記録が 1 つもない版 0 が存在します。

これから Q 個の操作が順に与えられます。

i 番目（1 \leq i \leq Q）の操作では、すでに存在する版 B（0 \leq B \leq i - 1）を参照し、操作の結果として新しい版 i が作られます。

操作には次の 2 種類があります。

  • 種類 0 ：0 B L R X

青木君が、版 B に対して「区間 [L, R] のスコアは X である」と主張します。

版 B で受理されているすべての記録およびこの主張を同時に満たすような、各要素が 0 以上 K-1 以下の整数である割り当て (A_1, A_2, \ldots, A_N) が存在するなら、この主張を受理して YES を出力してください。このとき、版 i は版 B の受理済み記録にこの主張を加えたものになります。

存在しないなら、この主張を却下して NO を出力してください。このとき、版 i は版 B と同じ内容になります。

  • 種類 1 ：1 B L R

高橋君が、版 B で受理されている記録だけから、区間 [L, R] のスコアが一意に決まるかを尋ねます。

版 B の受理済み記録をすべて満たすような割り当て (A_1, A_2, \ldots, A_N)（各要素は 0 以上 K-1 以下の整数）がどのようなものであっても区間 [L, R] のスコアが同じ値になるなら、その値を出力してください。

一意に決まらないなら UNKNOWN を出力してください。

この操作では新しい記録は追加されず、版 i は版 B と同じ内容になります。

Q 個の操作を順に処理し、各操作への答えを出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 2 \leq K \leq 10^9
  • 1 \leq Q \leq 10^5
  • i 番目の操作（1 \leq i \leq Q）において、0 \leq B \leq i - 1
  • 各操作において、1 \leq L \leq R \leq N
  • 種類 0 の操作において、0 \leq X \leq K - 1
  • 入力はすべて整数である

入力

N K Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

1 行目には、要素数 N、法 K、操作の数 Q がスペース区切りで与えられる。

続く Q 行には、操作が時系列順に与えられる。

種類 0 の操作は次の形式で与えられる。

0 B L R X

これは、版 B に対して「区間 [L, R] のスコアは X である」と主張する操作を表す。

種類 1 の操作は次の形式で与えられる。

1 B L R

これは、版 B において区間 [L, R] のスコアが一意に決まるかを尋ねる操作を表す。

出力

各操作に対する答えを、操作が与えられた順に Q 行出力してください。

  • 種類 0 の操作に対しては、主張を受理するなら YES、却下するなら NO を出力してください。
  • 種類 1 の操作に対しては、値が一意に決まるならその値を 0 以上 K - 1 以下の整数として出力し、一意に決まらないなら UNKNOWN を出力してください。

入力例 1

4 5 8
1 0 1 2
0 0 1 2 3
1 2 1 2
0 2 3 4 4
1 4 1 4
0 2 1 4 1
1 6 3 4
1 4 3 4

出力例 1

UNKNOWN
YES
3
YES
2
YES
3
4

入力例 2

3 7 7
0 0 1 3 2
0 1 1 1 4
0 2 2 3 5
0 2 2 3 6
1 4 2 3
0 4 1 3 3
0 0 1 3 3

出力例 2

YES
YES
YES
NO
5
NO
YES

入力例 3

8 10 18
0 0 1 4 6
0 1 5 8 3
1 2 1 8
0 2 3 6 7
1 4 1 2
0 4 1 2 9
1 6 3 6
0 6 1 8 0
1 8 1 8
0 4 1 2 1
1 10 5 6
0 10 5 6 3
1 12 7 8
0 0 2 7 4
1 14 1 8
0 14 1 1 2
0 16 8 8 5
1 17 1 8

出力例 3

YES
YES
9
YES
UNKNOWN
YES
7
NO
9
YES
2
NO
1
YES
UNKNOWN
YES
YES
1

入力例 4

20 1000000000 30
0 0 1 10 123456789
0 1 11 20 987654321
1 2 1 20
0 2 5 15 555555555
1 4 1 4
0 4 1 4 222222222
1 6 5 10
1 6 11 15
0 6 16 20 333333333
0 6 16 20 333333334
1 10 16 20
0 4 1 4 111111111
1 12 5 10
0 12 11 15 123456789
0 0 3 18 700000000
1 15 1 20
0 15 1 2 100000000
0 17 19 20 200000000
1 18 1 20
0 18 1 20 0
0 18 1 20 1
1 21 3 18
0 6 7 14 444444444
1 23 1 15
0 23 1 15 777777777
0 23 1 15 777777778
1 26 1 15
0 12 16 20 333333333
0 12 16 20 444444444
1 29 1 20

出力例 4

YES
YES
111111110
YES
UNKNOWN
YES
901234567
654320988
YES
NO
333333333
YES
12345678
NO
YES
UNKNOWN
YES
YES
0
YES
NO
700000000
YES
777777777
YES
NO
777777777
NO
YES
111111110

入力例 5

1 2 8
1 0 1 1
0 0 1 1 0
1 2 1 1
0 2 1 1 1
1 4 1 1
0 0 1 1 1
1 6 1 1
0 6 1 1 1

出力例 5

UNKNOWN
YES
0
NO
0
YES
1
YES

Score : 500 pts

Problem Statement

Takahashi and Aoki are trying to deduce N hidden integers A_1, A_2, \ldots, A_N.

Each A_i is an integer between 0 and K - 1 inclusive, but the specific values are unknown to both of them.

The score of an interval [L, R] is defined as the following value:

(A_L + A_{L+1} + \cdots + A_R) \bmod K

The two manage their deduction records as "versions" of a note.

Each operation references an existing version and produces a new version as its result. This causes versions to branch out in a tree structure.

Initially, there exists version 0, which contains no accepted records.

Q operations are given in order.

In the i-th operation (1 \leq i \leq Q), an already existing version B (0 \leq B \leq i - 1) is referenced, and a new version i is created as the result of the operation.

There are two types of operations:

  • Type 0: 0 B L R X

Aoki claims, with respect to version B, that "the score of interval [L, R] is X."

If there exists an assignment (A_1, A_2, \ldots, A_N) where each element is an integer between 0 and K-1 inclusive that simultaneously satisfies all records accepted in version B and this claim, then accept this claim and output YES. In this case, version i consists of the accepted records of version B plus this claim.

If no such assignment exists, reject this claim and output NO. In this case, version i has the same content as version B.

  • Type 1: 1 B L R

Takahashi asks whether the score of interval [L, R] can be uniquely determined from only the records accepted in version B.

If, for every assignment (A_1, A_2, \ldots, A_N) (where each element is an integer between 0 and K-1 inclusive) that satisfies all accepted records of version B, the score of interval [L, R] is the same value, then output that value.

If it cannot be uniquely determined, output UNKNOWN.

This operation does not add any new records, and version i has the same content as version B.

Process the Q operations in order and output the answer to each operation.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 2 \leq K \leq 10^9
  • 1 \leq Q \leq 10^5
  • In the i-th operation (1 \leq i \leq Q), 0 \leq B \leq i - 1
  • In each operation, 1 \leq L \leq R \leq N
  • In type 0 operations, 0 \leq X \leq K - 1
  • All inputs are integers

Input

N K Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

The first line contains the number of elements N, the modulus K, and the number of operations Q, separated by spaces.

The following Q lines contain the operations in chronological order.

A type 0 operation is given in the following format:

0 B L R X

This represents an operation where "the score of interval [L, R] is X" is claimed with respect to version B.

A type 1 operation is given in the following format:

1 B L R

This represents an operation asking whether the score of interval [L, R] can be uniquely determined in version B.

Output

Output the answer to each operation on Q lines, in the order the operations are given.

  • For type 0 operations, output YES if the claim is accepted, or NO if it is rejected.
  • For type 1 operations, if the value is uniquely determined, output that value as an integer between 0 and K - 1 inclusive; if it is not uniquely determined, output UNKNOWN.

Sample Input 1

4 5 8
1 0 1 2
0 0 1 2 3
1 2 1 2
0 2 3 4 4
1 4 1 4
0 2 1 4 1
1 6 3 4
1 4 3 4

Sample Output 1

UNKNOWN
YES
3
YES
2
YES
3
4

Sample Input 2

3 7 7
0 0 1 3 2
0 1 1 1 4
0 2 2 3 5
0 2 2 3 6
1 4 2 3
0 4 1 3 3
0 0 1 3 3

Sample Output 2

YES
YES
YES
NO
5
NO
YES

Sample Input 3

8 10 18
0 0 1 4 6
0 1 5 8 3
1 2 1 8
0 2 3 6 7
1 4 1 2
0 4 1 2 9
1 6 3 6
0 6 1 8 0
1 8 1 8
0 4 1 2 1
1 10 5 6
0 10 5 6 3
1 12 7 8
0 0 2 7 4
1 14 1 8
0 14 1 1 2
0 16 8 8 5
1 17 1 8

Sample Output 3

YES
YES
9
YES
UNKNOWN
YES
7
NO
9
YES
2
NO
1
YES
UNKNOWN
YES
YES
1

Sample Input 4

20 1000000000 30
0 0 1 10 123456789
0 1 11 20 987654321
1 2 1 20
0 2 5 15 555555555
1 4 1 4
0 4 1 4 222222222
1 6 5 10
1 6 11 15
0 6 16 20 333333333
0 6 16 20 333333334
1 10 16 20
0 4 1 4 111111111
1 12 5 10
0 12 11 15 123456789
0 0 3 18 700000000
1 15 1 20
0 15 1 2 100000000
0 17 19 20 200000000
1 18 1 20
0 18 1 20 0
0 18 1 20 1
1 21 3 18
0 6 7 14 444444444
1 23 1 15
0 23 1 15 777777777
0 23 1 15 777777778
1 26 1 15
0 12 16 20 333333333
0 12 16 20 444444444
1 29 1 20

Sample Output 4

YES
YES
111111110
YES
UNKNOWN
YES
901234567
654320988
YES
NO
333333333
YES
12345678
NO
YES
UNKNOWN
YES
YES
0
YES
NO
700000000
YES
777777777
YES
NO
777777777
NO
YES
111111110

Sample Input 5

1 2 8
1 0 1 1
0 0 1 1 0
1 2 1 1
0 2 1 1 1
1 4 1 1
0 0 1 1 1
1 6 1 1
0 6 1 1 1

Sample Output 5

UNKNOWN
YES
0
NO
0
YES
1
YES