The Everbinding War finally ended after the Battle of Wellacotia. The Collean Government, realizing the futility of continuing the war, shortly surrendered afterwards. As such, the agreement signed to end the conflict is to be known as the Wellacotia Treaty. The Wellacotia Treaty consists of ~N~ terms, with each one being applied to exactly one of the ~K~ countries. The ~i~th term of the treaty is applied to country ~a_i~, where each country is represented by an integer between ~1~ and ~K~. However, before the signing of the treaty, each of the ~M~ diplomats at the conference decided to reorder a segment of the terms of the treaty. In particular, the ~i~th diplomat would choose the segment ~[l_i,r_i]~, such that terms applying to their first favourite country come first, terms applying to their second favourite country would follow, and so on. The list of preferences of the ~i~th diplomat is ~p_{i,1}, p_{i,2}, \dots, p_{i,K}~, where ~p_{i,j}~ is their ~j~th favourite country.

The Quatryian government believes that Wellacotia has altered the terms on their copy of the treaty. They know the order of the original terms on the treaty, as well as the changes made by each diplomat. Help them determine the final order of the terms of the Wellacotia Treaty. Since this might be a little too difficult, they instead ask you to determine the country that each term of the treaty applies to.

Constraints

In all subtasks,
~1 \le N \le 100\,000~
~1 \le M \le 50\,000~
~2 \le K \le 20~
~p_{i,1}, p_{i,2}, \dots, p_{i,K}~ is a permutation of ~1, 2, \dots, K~.

Subtask 1 [5%]

~1 \le N,M \le 100~

Subtask 2 [20%]

~1 \le N,M \le 1000~

Subtask 3 [25%]

~K = 2~

Subtask 4 [50%]

No additional constraints.

Input Specification

The first line contains three integers, ~N~, ~M~ and ~K~.
The second line contains ~N~ integers, ~a_1, a_2, \dots, a_N~.
For each of the ~M~ updates, two lines are given. On the ~i~th update, the first line contains ~l_i~ and ~r_i~, while the second line contains the integers ~p_{i,1}, p_{i,2}, \dots, p_{i,K}~, the list of the ~i~th diplomat's favourite countries.

Output Specification

Output one line consisting of ~N~ integers, the ~i~th integer being the country to which the ~i~th term of the treaty is applied to.

Sample Input

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

Sample Output

1 2 3 1 3