Background

小北看了《飞驰人生2》，觉得非常好看。

Description

给出一个长度为 $m$ 的序列 $b(b_i \leq m)$。

• 对于数字 $x(x\leq m)$，如果它进行了一次“飞驰”操作，那它就会变成 $b_{x}$。

再给出一个长度为 $n$ 的序列，第 $i$ 个数为 $a_i(a_i \leq m)$。

共 $q$ 次在 $a$ 序列上发生的操作，每次操作形如 $[l,r,k]$，表示将 $[l,r]$ 区间里的所有数字都进行 $k$ 次飞驰操作。

请你输出 $q$ 次操作后序列 $a$ 的样子。

Format

Input

第一行 $3$ 个整数分别代表 $m,n,q$。

第二行 $m$ 个整数代表序列 $b$。

第三行 $n$ 个整数代表序列 $a$。

后面 $q$ 行，每行一个操作。

Output

输出 $n$ 个整数，代表最终的序列 $a$。

Samples

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

2 1 2 1

5 5 5
3 4 2 3 1
5 4 3 2 1
2 4 89
1 3 23
4 4 11
2 5 34
1 5 74

4 3 2 4 4

Limitation

对于 $20\%$ 的数据，$n,m,k \leq 500$

对于 $50\%$ 的数据，$n,m,k \leq 2000$

对于 $100\%$ 的数据，$n,m,k \leq 2 \times 10^5$