아기 석환이

석환이는 4살 귀여운 아기다. 선생님인 수랄은 석환이에게 아기에게 맞는 지식을 가르치고 있다. 수랄은 커다란 화이트보드를 가져왔는데, 이는 사실상 크기가 $M$인 빈 벡터(모든 원소가 0인 벡터) $N$개 $V_1, V_2, \cdots, V_N$과 같다.

어제 석환이는 숫자 쓰는 법을 배웠다. 능력을 확인하려고 수랄은 석환이에게 $Q$개의 질의를 주었다. 각 질의는 정수 네 개 $S, E, P, X$로 주어진다. 벡터 $V_S, V_{S+1}, \cdots, V_E$ 모두에 대해, 각 벡터의 $P$번째 원소에 $X$를 쓴다. 석환이는 이미 값을 쓴 자리에 다시 쓰지 않는다.

오늘 석환이는 수열을 $O(N\log N)$ 시간에 정렬하는 법을 배웠다. 능력을 확인하려고 수랄은 석환이에게 벡터를 정렬하라고 한다. 석환이는 크기가 $N$인 순열 $P_1, P_2, \cdots, P_N$을 찾아야 하며, 모든 $1 \leq i < N$에 대해 $V_{P_i} \leq V_{P_{i+1}}$이어야 한다. 수랄은 안정 정렬을 원하므로, 조건을 만족하는 순열이 여럿이면 사전순으로 가장 작은 것을 출력한다. 길이가 같은 두 수열 $L$과 $R$에 대해, 어떤 $j \in [1, M]$이 존재하여 모든 $1 \leq i < j$에 대해 $L_i = R_i$이고 $L_j < R_j$이면 $R$이 $L$보다 사전순으로 크다.

석환이는 이 작업을 모두 8000ms 안에 해냈지만, 수랄은 그 방법을 모른다. 수랄을 돕기 위해 석환이가 한 일을 그대로 재현하라.

첫째 줄에 벡터의 개수 $N$, 각 벡터의 크기 $M$, 질의의 개수 $Q$가 주어진다.

다음 $Q$개의 줄에는 정수 네 개 $S, E, P, X$가 주어진다. 이는 벡터 $V_S, \cdots, V_E$ 모두의 $P$번째 원소에 $X$를 쓰라는 뜻이다.

$i$번째 줄에, 모든 $1 \leq i < N$에 대해 $V_{P_i} \leq V_{P_{i+1}}$을 만족하는 순열 $P_1, P_2, \cdots, P_N$ 중 사전순으로 가장 작은 순열의 $i$번째 원소를 출력한다.

$1 \leq N, M, Q \leq 250000$

각 질의에 대해 다음을 만족한다.

• $1 \leq S \leq E \leq N$
• $1 \leq P \leq M$
• $1 \leq X \leq 250000$