← 返回题目列表

Codeforces · 911/G

G. 批量更改查询

中文机器翻译题面 查看原题

给定一个由 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