Background

The testdata on Luogu is for non-official communication only and is not official testdata. Official judging link: https://www.cspro.org/。

Problem Description

Little C is very interested in how computers work, and often does research and experiments.

One day, when he tried to delete a file of several GB, he was surprised to find that the deletion finished almost instantly. This confused him: if the computer really erased the corresponding data on the disk every time it deleted a file, shouldn’t it take a long time?

So he invited Little S and Little P to discuss it together. Little S said that maybe the computer system is very “lazy” and does not actually erase the data when deleting. Little P, being more experienced, immediately found a piece of software that claimed it could “recover disk data”, and on the spot recovered the file that Little C had just deleted!

This made Little C even more curious, so they decided to design a model to simulate the process of writing, deleting, and recovering disk files. However, on Xixiaifu Island where they live, there are no suitable conditions to run their model, so they contacted you, who is traveling to Xixiaifu Island with a super powerful computer, to help them.

In the model designed by Little C, Little S, and Little P, there are $n$ programs in the computer (numbered $1 \sim n$). They share a disk space of size $m$ (numbered $1 \sim m$), and each position on the disk can store an integer.

Initially, every position on the disk stores $0$ and is not occupied by any program.

Now these $n$ programs run simultaneously. At some moment, a program may perform operations such as reading or writing disk data.

There are $k$ operations, given in chronological order, as follows:

$0\ id\ l\ r\ x$: Program $id$ tries to write an integer $x$ to every position in $[l, r]$ on the disk.

• During the operation, program $id$ tries to write from the left end $l$ to the right in order.
• For each position, if it is currently not occupied by any program, the write of $x$ succeeds, and the position is considered occupied by program $id$.
• If the position is currently occupied by program $id$ itself, the new $x$ can overwrite the previous value, and the position is still occupied by program $id$ afterward.
• The operation continues until it successfully writes to position $r$, or it meets the first position that is occupied by another program. In the latter case, the operation is interrupted immediately.

$1\ id\ l\ r$: Program $id$ tries to delete all data in positions $[l, r]$ on the disk.

• This operation can succeed if and only if all positions in $[l, r]$ are currently occupied by program $id$.
• If it succeeds, all positions in the interval become unoccupied, i.e. they return to a state where any program can write. However, to make data recovery possible, the stored values are not immediately overwritten back to $0$.
• Otherwise, the operation is considered to fail and no changes are made.

$2\ id\ l\ r$: Program $id$ tries to recover all data in positions $[l, r]$ on the disk.

• This operation can succeed if and only if all positions in $[l, r]$ are currently unoccupied, and the last program that occupied them was program $id$.
• If it succeeds, all positions in the interval are restored to the state of being occupied by program $id$. Since the previous delete operation did not change the stored values, this operation also does not need to modify the value at each position.
• Otherwise, the operation is considered to fail and no changes are made.

$3\ p$: Try to read the data at position $p$ on the disk, and return two integers.

• If the position is currently occupied by program $id$ and the stored value is $p$, return $id\ p$.
• If the position is currently not occupied by any program, return $0\ 0$.

You need to implement a program to help Little C, Little S, and Little P simulate the process above, and output the result for each operation.

Input Format

Read from standard input.

The first line: $3$ positive integers $n, m, k$.

The next $k$ lines: each line contains several integers describing one operation, in the format described above.

Output Format

Output to standard output.

Output a total of $k$ lines, one line for each operation.

• For each write operation, output one integer indicating the rightmost position successfully written in this operation. In particular, if the operation does not successfully write to any position, output $-1$.
• For each delete or recover operation, if it succeeds output the string OK, otherwise output the string FAIL.
• For each read operation, output two integers indicating the result of the query.

3 15 12
0 1 1 5 -1
0 2 10 13 2
0 1 4 14 6
1 1 2 8
3 1
3 3
3 14
2 1 3 5
0 3 7 8 -4
2 1 6 8
1 3 6 7
0 2 5 7 3

5
13
9
OK
1 -1
0 0
0 0
OK
8
FAIL
FAIL
-1

Hint

Sample 2

See 2.in and 2.ans under the problem directory.

Sample 3

See 3.in and 3.ans under the problem directory.

Subtasks

• For $25\%$ of the data, $n, k \leq 2000$, $m \leq 10000$.
• For another $15\%$ of the data, there are no delete or recover operations.
• For another $20\%$ of the data, there are no recover operations.
• For another $15\%$ of the data, $n = 1$.
• For $100\%$ of the data, $1 \leq n, k \leq 2 \times 10^5$, $1 \leq m \leq 10^9$, $1 \leq id \leq n$, $1 \leq l \leq r \leq m$, $1 \leq p \leq m$, $|x| \leq 10^9$.

Translated by ChatGPT 5