Scheduler

Time Limit : 2 sec, Memory Limit : 262144 KB

スケジューラ

あなたはユニークなオペレーティングシステム「ウンズグネ15」の開発に取り組んでおり、性能を決定付けるスケジューラの設計に頭を悩ませている。スケジューラとは、実行すべき処理をタスクという単位で表現し、それらをどの順序で実行するかを決定するプログラムである。スケジューラはタスクに1から N の番号をつけて管理する。全てのタスクは K 個の属性 f1, f2,..., fK を持ち、各属性にはそれぞれ固有の値が設定されている。ただし、ある2つのタスクについて、対応する属性の値すべてが同じになることはない。

あるタスクには、そのタスクの実行を始める前までに実行を完了していなければならないタスクが与えられることがある。タスクAがタスクBの前に完了していなければならないことを「タスクA → タスクB」と表す。例えば、タスク1 → タスク2、タスク3 → タスク2という関係があれば、タスク2を処理する前にタスク1とタスク3の両方の処理が終わっていなければならない。このような関係をタスク間の依存関係という。ただし、あるタスクから依存関係をたどっていって、そのタスクにたどり着くことはない。

スケジューラは依存関係に従って、実行順序を決定する。しかし、依存関係だけでは順序が一通りに定まらない場合がある。そのような場合は、各タスクが持つ属性の値によって、次に処理するタスクを選択する。

ウンズグネ15のタスクは属性を複数もつため、すべての属性の値を考慮して実行順序を決定する必要がある。そのために、属性を比較する順番を定める評価順序を用いる。評価順序が最も先の属性を比較し、その属性の値が最も大きいタスクを選択する。そのようなタスクが複数ある場合は、評価順序がその次の属性で比較し、以下同様な手順を繰り返す。例えば、以下の3 つの属性を持つ3 つのタスクについて考える。

タスク\属性 f1 f2 f3
X 3 3 2
Y 3 2 2
Z 3 1 3

評価順序がf1 f2 f3f2 f1 f3、または f2 f3 f1 に設定されている場合は、タスクX が選ばれる。また、評価順序が f1 f3 f2f3 f1 f2、または f3 f2 f1 に設定されている場合はタスクZ が選ばれる。

ウンズグネ15のスケジューラの特徴は、属性の評価順序が途中で何度でも変更できることである。評価順序は、ある個数のタスクの実行が完了した時点で変更できる。ただし、スケジューラが最初に使う評価順序はあらかじめ決まっている。

各タスクの属性の値、タスクの依存関係、評価順序の変更情報が与えられたとき、タスクを実行する順序を報告するプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

N K
f1,1 f1,2 ... f1,K
f2,1 f2,2 ... f2,K
:
fN,1 fN,2 ... fN,K
D
a1 b1
a2 b2
:
aD bD
e0,1 e0,2 ... e0,K
R
m1 e1,1 e1,2 ...… e1,K
m2 e2,1 e2,2 ...… e2,K
:
mR eR,1 eR,2 ...… eR,K

1行目に、タスクの数 N (2 ≤ N ≤ 50000) と、各タスクが持つ属性の数 K (1 ≤ K ≤ 4) が与えられる。続く N 行に、タスク i が持つ属性の値 fi,j (1 ≤ fi,j ≤ 100000) が与えられる。続く1行に、依存関係の個数 D (0 ≤ D ≤ 200000) が与えられる。続く D 行に依存関係 aibi (1 ≤ ai, biN) が与えられる。

続く1行に、最初の評価順序 e0,j (1 ≤ e0,jK) が与えられる。続く1行に、評価順序の変更回数 R (0 ≤ R < N) が与えられる。続く R 行に、評価順序の変更情報が与えられる。i 回目の変更情報は、実行が完了したタスクの個数 mi (1 ≤ mi < N) と評価順序 ei,j (1 ≤ ei,jK) からなり、全部で mi 個のタスクの実行が完了した時点で、評価順序を ei,1, ei,2,... , ei,K に変更することを示す。

評価順序の変更情報は以下の条件を満たす。

  • ei,1, ei,2,..., ei,K 中に同じ値は2つ以上現れない。
  • i < j のとき、 mi < mj である。

Output

スケジューラが処理する順番に、タスクの番号を出力する。

Sample Input 1

5 3
1 5 2
3 8 5
1 2 3
5 5 5
4 8 2
0
1 2 3
2
2 2 3 1
4 3 1 2

Sample Output 1

4
5
2
1
3

Sample Input 2

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

Sample Output 2

3
2
5
1
4

Source: PC Koshien 2015 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2015-11-7
http://web-ext.u-aizu.ac.jp/pc-concours/