C. Meximum Array 2
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Example
Input
4
6 2 2
1 1 3
2 2 6
3 3 1
2 1 3
3 3 2
1 1 1
1 3 3
3 2 2
2 1 2
2 2 3
Output
2 5 4 3 0 1
2 0 1
3 3 3
1 0 1
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]$$$.