Seokhwan 是一个 4 岁的可爱宝宝。他的老师 Suryal 正在教他一些适合宝宝的知识。 Suryal 带来了一块大白板，上面本质上有 $N$ 个大小为 $M$ 的空向量（初始全为零），记作 $V_1, V_2, \dots, V_N$。

昨天，Seokhwan 学习了如何写数字。为了测试他的能力，Suryal 给 Seokhwan 出了 $Q$ 个查询。对于每个查询，Seokhwan 会得到四个数字 $S, E, P, X$。对于所有向量 $V_S, V_{S+1}, \dots, V_E$，Seokhwan 需要将 $X$ 写入每个向量的第 $P$ 个位置。保证 Seokhwan 从不覆盖（他从不在已经写过数字的地方再次写入）。

今天，Seokhwan 学习了如何以 $O(N \log N)$ 的时间复杂度对序列进行排序。为了测试他的能力，Seokhwan 需要对这些向量进行排序。形式化地，Seokhwan 需要找到一个大小为 $N$ 的排列 $P_1, P_2, \dots, P_N$，使得对于所有 $1 \le i < N$，满足 $V_{P_i} \le V_{P_{i+1}}$。Suryal 希望 Seokhwan 进行稳定排序，因此如果有多个这样的排列 $P$，你应该输出字典序最小的那一个。

Seokhwan 在 5 秒内完成了所有这些任务，而 Suryal 不知道他是怎么做到的。你应该帮助 Suryal，并完成 Seokhwan 所做的事情。对于两个相同大小的序列 $L$ 和 $R$，$R$ 的字典序大于 $L$ 当且仅当存在某个 $j \in [1, M]$，使得对于所有 $1 \le i < j$ 都有 $L_i = R_i$，且 $L_j < R_j$。

输入格式

第一行包含向量的数量 $N$、每个向量的大小 $M$ 以及查询的数量 $Q$。 $(1 \le N, M, Q \le 250000)$

接下来的 $Q$ 行，每行给出四个整数 $S, E, P, X$。这表示对于所有向量 $V_S, V_{S+1}, \dots, V_E$，Seokhwan 需要将 $X$ 写入每个向量的第 $P$ 个位置。$(1 \le S, E \le N, 1 \le P \le M, 1 \le X \le 250000)$。

输出格式

在第 $i$ 行，打印排列的第 $i$ 个元素，即满足 $V_{P_i} \le V_{P_{i+1}}$ 的字典序最小的排列。

样例

输入格式 1

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

输出格式 1

1
5
3
4
2