CF2157C Meximum Array 2

[Ferus Melek - Brute Force](https://soundcloud.com/ferusmelek/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 $ .

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.

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

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