문제

민혁이는 $N$개의 정수로 이루어진 배열 $a$를 만들려고 한다. 배열의 각 원소 $a_i$는 $0$ 이상 $10^9$ 이하의 정수여야 한다. 승현이는 이 배열이 만족해야 할 $Q$개의 제약 조건을 주었다. 각 제약 조건은 네 정수 $t_i, l_i, r_i, k_i$로 이루어져 있으며, 내용은 다음과 같다.

• $t_i = 1$인 경우: $\min(a_{l_i}, a_{l_i+1}, \dots, a_{r_i}) = k_i$
• $t_i = 2$인 경우: $\max(a_{l_i}, a_{l_i+1}, \dots, a_{r_i}) = k_i$

모든 $k_i$는 서로 다르다. 승현이가 준 모든 조건을 만족하는 배열 $a$를 하나 생성하시오. 만약 조건을 만족하는 배열이 여러 개라면 그중 아무거나 하나를 출력한다. 조건을 만족하는 배열을 만들 수 없다면 -1을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10^4$)

각 테스트 케이스의 첫째 줄에 정수 $N$과 $Q$가 공백으로 구분되어 주어진다. ($1 \le N, Q \le 2 \cdot 10^5$)

이어서 $Q$개의 줄에 각 제약 조건을 나타내는 네 정수 $t_i, l_i, r_i, k_i$가 공백으로 구분되어 주어진다. ($1 \le t_i \le 2$; $1 \le l_i \le r_i \le N$; $0 \le k_i \le 10^9$)

모든 테스트 케이스에 대해 $N$의 총합과 $Q$의 총합은 각각 $2 \cdot 10^5$를 넘지 않으며, 각 테스트 케이스 내의 모든 $k_i$는 서로 다르다.

출력

각 테스트 케이스마다 조건을 만족하는 배열이 존재한다면 $N$개의 정수 $a_1, a_2, \dots, a_N$을 공백으로 구분하여 출력한다. 존재하지 않는다면 -1을 출력한다.

서브태스크

• 테스트 케이스 3-4: $N, Q \le 100$이며, 하나의 테스트 케이스 내의 모든 $t_i$는 동일하다.
• 테스트 케이스 5-6: 하나의 테스트 케이스 내의 모든 $t_i$는 동일하다.
• 테스트 케이스 7-10: $N, Q \le 100$.
• 테스트 케이스 11-14: 추가 제약 조건이 없다.