对于类型 $1$ 的限制，每个点肯定要 $\ge k_{\max}$，对于类型 $2$ 的限制，每个点肯定要 $\le k_{min}$，同时注意到取上下界肯定不劣于取中间。

考虑建图，因为 $k$ 互不相同，考虑以每个限制编号为点，原序列上的位置为边权。连一条上下界的边，即在 $id_{k_{\max}}$ 和 $id_{k_{\min}}$ 中连边。若其中有一个没有限制，则连一条自环。

则原问题变为给你若干个连通块，你要给所有边定向使得每个点的入度大于 $0$。其实际意义为每个位置满足一个限制条件使得所有限制都被满足。

对于每个连通块，先找一棵生成树，然后找一条非树边，构成一个基环树，从环上走一圈并以环上每个点开始构造一棵外向树。

注意实现上的细节，可以离线用线段树求 $k_{\min}$ 和 $k_{\max}$，然后用并查集维护生成树并找非树边。

#include <bits/stdc++.h>
#define rd read()
using namespace std;
inline int read() {
	int x = 0; char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return x;
}
const int N = 2e5 + 5;
struct Node {int l, r, k;};
vector<Node> v1, v2;
vector<pair<int, int>> g[N];
vector<tuple<int, int, int>> G[N];
unordered_map<int, int> mp;
inline bool cmp1(Node x, Node y) {return x.k < y.k;}
inline bool cmp2(Node x, Node y) {return x.k > y.k;}
int n, q, mn[N], mx[N], dep[N], vis[N], fa[N], Fa[N], W[N], a[N], p[N];
struct Segment {
	int tag[N << 2];
	void init() {for (int i = 0; i <= n * 4; ++i) tag[i] = -1;}
	inline void pushdown(int k) {if (~tag[k]) tag[k << 1] = tag[k << 1 | 1] = tag[k], tag[k] = -1;}
	inline void modify(int k, int l, int r, int L, int R, int v) {
		if (l >= L && r <= R) return tag[k] = v, void();
		int mid = l + r >> 1; pushdown(k);
		if (mid >= L) modify(k << 1, l, mid, L, R, v);
		if (mid < R) modify(k << 1 | 1, mid + 1, r, L, R, v);
	}
	inline int ask(int k, int l, int r, int p) {
		if (l == r) return tag[k];
		int mid = l + r >> 1; pushdown(k);
		return (mid >= p ? ask(k << 1, l, mid, p) : ask(k << 1 | 1, mid + 1, r, p));
	}
} T;
inline int find(int x) {
	if (x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}
inline void merge(int x, int y, int w) {
	int fx = find(x), fy = find(y);
	if (fx == fy) return G[x].push_back({x, y, w}), void();
	fa[fy] = fx; g[x].push_back({y, w}), g[y].push_back({x, w});
}
void dfs1(int u) {
	for (auto [v, w] : g[u]) 
		if (v != Fa[u]) dep[v] = dep[u] + 1, Fa[v] = u, dfs1(v), W[v] = w;
}
void dfs2(int u) {
	vis[u] = 1;
	for (auto [v, w] : g[u]) 
		if (!vis[v]) a[w] = p[v], dfs2(v);
}
inline void solve(int x, int y, int w) {
	vector<int> S; a[w] = p[x]; 
	while (x != y) {
		if (dep[Fa[x]] > dep[Fa[y]]) a[W[x]] = p[Fa[x]], vis[Fa[x]] = 1, S.push_back(x), x = Fa[x];
		else a[W[y]] = p[y], vis[Fa[y]] = 1, S.push_back(y), y = Fa[y];
	}S.push_back(x);
	for (auto i : S) dfs2(i);
}
inline void solve() {
	n = rd, q = rd; mp.clear(), v1.clear(), v2.clear(); T.init(); dep[0] = -1;
	for (int i = 1; i <= max(n, q); ++i) mx[i] = mn[i] = -1, g[i].clear(), G[i].clear(), dep[i] = vis[i] = 0, fa[i] = i, Fa[i] = 0, W[i] = p[i] = 0;
	for (int i = 1, t, l, r, k; i <= q; ++i) { 
		t = rd, l = rd, r = rd, k = rd; p[i] = k;
		mp[k] = i;
		if (t == 1)v1.push_back({l, r, k});
		else v2.push_back({l, r, k});
	}
	sort(v1.begin(), v1.end(), cmp1);
	sort(v2.begin(), v2.end(), cmp2);
	for (auto [l, r, k] : v1) T.modify(1, 1, n, l, r, k);
	for (int i = 1; i <= n; ++i) {
		int v = T.ask(1, 1, n, i); 
		if (~v) mn[i] = v;
	}
	T.init();
	for (auto [l, r, k] : v2) T.modify(1, 1, n, l, r, k);
	for (int i = 1; i <= n; ++i) {
		int v = T.ask(1, 1, n, i);
		if (~v) mx[i] = v;
	} 
	for (int i = 1; i <= n; ++i) if (~mn[i] && ~mx[i] && mn[i] > mx[i]) return cout << -1 << '\n', void();
	for (int i = 1; i <= n; ++i) {
		if (~mn[i] && ~mx[i]) merge(mp[mx[i]], mp[mn[i]], i), a[i] = mn[i];
		else if (~mn[i]) merge(mp[mn[i]], mp[mn[i]], i), a[i] = mn[i];
		else if (~mx[i]) merge(mp[mx[i]], mp[mx[i]], i), a[i] = mx[i];
	}
	for (int i = 1; i <= q; ++i) if (find(i) == i) dfs1(i); 
	for (int i = 1; i <= q; ++i) {
		if (vis[find(i)]) continue ;
		for (auto [x, y, w] : G[i]) {solve(x, y, w); break; }
	}
	for (int i = 1; i <= q; ++i) if (!vis[i]) return cout << -1 << '\n', void();
	for (int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << '\n';
}
signed main() {
	int t = rd; while (t--) solve();
	return 0;
}