Ferus Melek - Brute Force⠀

You are given three positive integers $n$, $k$, and $q$. You are also given $q$ tuples $(c, l, r)$, with $1 \leq c \leq 2$ and $1 \leq l \leq r \leq n$.

An array $a_1, a_2, \ldots, a_n$ is meximum if $0 \leq a_i \leq 10^9$ for each $i$ in $[1, n]$, and for each given tuple $(c, l, r)$,

• if $c = 1$, then $\min(a_l, a_{l+1}, \ldots, a_r) = k$;
• if $c = 2$, then $\operatorname{MEX}$$^{\text{∗}}$$(a_l, a_{l+1}, \ldots, a_r) = k$.

Note that the parameter $k$ is the same for all the conditions.

Find a meximum array $a_1, a_2, \ldots, a_n$ of length $n$. The input is generated in such a way that a valid array always exists. If there are multiple possible arrays, you can print any one of them.

$^{\text{∗}}$The minimum excluded (MEX) of a collection of integers $a_1, a_2, \ldots, a_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $a$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $k$, $q$ ($1 \leq k \leq n \leq 100$, $1 \leq q \leq 100$) — the length of the array $a_1, a_2, \ldots, a_n$, the result of the $\min$ and $\operatorname{MEX}$ calculations described by the tuples, and the number of tuples.

Then, $q$ lines follow. The $i$-th line contains a tuple $(c, l, r)$, which gives a constraint to $a_l, a_{l+1}, \ldots, a_r$ according to the statement.

It is guaranteed that there exists a valid array corresponding to the given input.

Note that there are no constraints on the sum of $n$, $k$, or $q$ over all test cases.

Output

For each test case, print a single line containing a meximum array $a_1, a_2, \ldots, a_n$.

Note

In the first test case, you have to build a meximum array with $n = 6$, $k = 2$ and with $q = 2$ constraints given by tuples.

• tuple $(1, 1, 3)$: $\min(a_1, a_2, a_3)$ must be $2$;
• tuple $(2, 2, 6)$: $\operatorname{MEX}(a_2, a_3, a_4, a_5, a_6)$ must be $2$.

A possible array that satisfies all these constraints, and has elements $0 \leq a_i \leq 10^9$, is $[2, 5, 4, 3, 0, 1]$.

In the second test case, you have to build a meximum array with $n = 3$, $k = 3$ and with $q = 1$ constraint given by a tuple.

• tuple $(2, 1, 3)$: $\operatorname{MEX}(a_1, a_2, a_3)$ must be $3$.

A possible array that satisfies this constraint, and has elements $0 \leq a_i \leq 10^9$, is $[2, 0, 1]$.