The Treaty of Wellacotia

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.75s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 ith 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 ith 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 ith diplomat is p_{i,1},p_{i,2} \ldots p_{i,K}, where p_{i,j} is their jth 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.


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} \ldots 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%]


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\ldots a_N.
For each of the M updates, two lines are given. On the ith update, the first line contains l_i and r_i, while the second line contains the integers p_{i,1},p_{i,2} \ldots p_{i,K}, the list of the ith diplomat's favourite countries.

Output Specification

Output one line consisting of N integers, the ith integer being the country to which the ith 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


  • 5
    revlis  commented on Dec. 27, 2018, 5:29 p.m.

    there is a problem in the judging please fix it

    • 5
      Kirito  commented on Dec. 27, 2018, 6:12 p.m.

      Issue has been resolved, and all affected submissions rejudged.