CF1697F Too Many Constraints

You are asked to build an array $ a $ , consisting of $ n $ integers, each element should be from $ 1 $ to $ k $ . The array should be non-decreasing ( $ a_i \le a_{i+1} $ for all $ i $ from $ 1 $ to $ n-1 $ ). You are also given additional constraints on it. Each constraint is of one of three following types: - $ 1~i~x $ : $ a_i $ should not be equal to $ x $ ; - $ 2~i~j~x $ : $ a_i + a_j $ should be less than or equal to $ x $ ; - $ 3~i~j~x $ : $ a_i + a_j $ should be greater than or equal to $ x $ . Build any non-decreasing array that satisfies all constraints or report that no such array exists.

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains three integers $ n, m $ and $ k $ ( $ 2 \le n \le 2 \cdot 10^4 $ ; $ 0 \le m \le 2 \cdot 10^4 $ ; $ 2 \le k \le 10 $ ). The $ i $ -th of the next $ m $ lines contains a description of a constraint. Each constraint is of one of three following types: - $ 1~i~x $ ( $ 1 \le i \le n $ ; $ 1 \le x \le k $ ): $ a_i $ should not be equal to $ x $ ; - $ 2~i~j~x $ ( $ 1 \le i < j \le n $ ; $ 2 \le x \le 2 \cdot k $ ): $ a_i + a_j $ should be less than or equal to $ x $ ; - $ 3~i~j~x $ ( $ 1 \le i < j \le n $ ; $ 2 \le x \le 2 \cdot k $ ): $ a_i + a_j $ should be greater than or equal to $ x $ . The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^4 $ . The sum of $ m $ over all testcases doesn't exceed $ 2 \cdot 10^4 $ .

For each testcase, determine if there exists a non-decreasing array that satisfies all conditions. If there is no such array, then print -1. Otherwise, print any valid array — $ n $ integers from $ 1 $ to $ k $ .