给定一个由 n 个整数组成的数组 a。您必须处理对此数组的 q 个查询;每个查询由四个数字 l、r、x 和 y 给出,表示对于每个 i,使得 l ≤ i ≤ r 且 ai = x,您必须将 ai 设置为等于 y。
处理所有查询后打印数组。
输入
第一行包含一个整数 n (1 ≤ n ≤ 200000) — 数组 a 的大小。
第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 100) — 数组 a 的元素。
第三行包含一个整数 q (1 ≤ q ≤ 200000) — 您必须处理的查询数。
接下来是 q 行。第 i 行包含四个整数 l、r、x 和 y,表示第 i 个查询 (1 ≤ l ≤ r ≤ n, 1 ≤ x, y ≤ 100)。
输出
打印 n 个整数 — 进行所有更改后数组 a 的元素。
示例
输入 #1
5 1 2 3 4 5 3 3 5 3 5 1 5 5 1 1 5 1 5
输出 #1
5 2 5 4 5