Seokhwan is a cute 4-year-old baby. His teacher, Suryal, is teaching some knowledge suited for babies. Suryal brought a big whiteboard, which is essentially $N$ empty vectors (vectors filled with zeroes) of size $M$, denoted by $V_1, V_2, \dots, V_N$.

Yesterday, Seokhwan learned how to write numbers. To test his ability, Suryal gave $Q$ queries to Seokhwan. For each query, Seokhwan is given four numbers $S, E, P, X$. For all vectors $V_S, V_{S+1}, \dots, V_E$, Seokhwan should write $X$ to the $P$-th element of each vector. It’s guaranteed that Seokhwan never overwrites (he never writes in a place where he already wrote something).

Today, Seokhwan learned how to sort a sequence in $O(N \log N)$ time complexity. To test his ability, Seokhwan should sort the vectors. Formally, Seokhwan should find a size-$N$ permutation $P_1, P_2, \dots, P_N$ where $V_{P_i} \le V_{P_{i+1}}$ for all $1 \le i < N$. Suryal expects Seokhwan to do stable sort, thus if there are many such $P$, then you should print the one which is lexicographically minimum.

Seokhwan did all those tasks in 5 seconds, which Suryal doesn't know how. You should help Suryal, and do what Seokhwan did. For two sequences $L, R$ of the same size, $R$ is lexicographically greater than $L$ if and only if there exists some $j \in [1, M]$ such that $L_i = R_i$ for all $1 \le i < j$ and $L_j < R_j$.

Input

The first line contains the number of vectors $N$, size of each vector $M$, and number of queries $Q$. ($1 \le N, M, Q \le 250000$)

In the next $Q$ lines, four integers $S, E, P, X$ are given. This indicates that for all vectors $V_S, V_{S+1}, \dots, V_E$, Seokhwan should write $X$ to the $P$-th element of each vector. ($1 \le S, E \le N$, $1 \le P \le M$, $1 \le X \le 250000$).

Output

In the $i$-th line, print the $i$-th element of the permutation, which is the lexicographically minimum permutation for which $V_{P_i} \le V_{P_{i+1}}$ holds.

Examples

Input 1

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

Output 1

1
5
3
4
2