时空限制

1S/256M

题目描述

元旦假期当然要玩好玩的游戏，于是 apiadu 和 jiangly 在一个长度为 $n$ 的序列 $a$ 上面玩游戏。游戏一共有 $q$ 轮，第 $i$ 轮游戏将在子数组 $a_{l_i},\dots,a_{r_i}$ 上进行，且第 $i$ 轮游戏有一个参数 $t_i\in\{0,1\}$。每轮游戏都是独立的，也就是说每轮游戏结束后序列都会恢复初始状态。

一轮游戏的规则如下：

apiadu 先手，jiangly 后手，两人的初始分数都是 $0$。两人轮流取走数组中的一个值并将这个值异或到自己的分数上，直到数组为空。若这一轮游戏的参数 $t_i=0$，则 apiadu 获胜当且仅当游戏结束后两人分数相同，否则 apiadu 获胜当且仅当游戏结束后两人分数不同。

现在数组 $a$ 还没有确定，apiadu 需要你帮他构造一个权值在 $[1,10^9]$ 范围内的序列使得这 $q$ 轮游戏他都有必胜策略。

格式

输入格式

本题包含多组测试数据。

第一行一个正整数 $T$ 表示数据组数。

对于每组数据，第一行两个正整数 $n,q$ 分别表示序列长度以及游戏轮数。

对于每组数据，接下来的 $q$ 行，每行三个整数 $l_i,r_i,t_i$ 分别表示这一轮游戏所在的子数组以及游戏参数。

输出格式

对于每组数据，如果无解输出一行一个整数 -1。

否则输出一行 $n$ 个在 $[1,10^9]$ 范围内的正整数表示你构造的序列。如果存在多种构造方案，输出任意一种即可。

样例

样例输入 #1

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

样例输出 #1

5 1 4 5 5 
-1

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le \sum n, \sum q \le 3 \times 10^5$，$1 \le l_i \le r_i \le n$，$t_i \in \{0, 1\}$。