0852 - スケジューラ

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

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

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

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

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

評価順序がf₁ f₂ f₃、f₂ f₁ f₃、または f₂ f₃ f₁ に設定されている場合は、タスクX が選ばれる。また、評価順序が f₁ f₃ f₂、f₃ f₁ f₂、または f₃ f₂ f₁ に設定されている場合はタスクZ が選ばれる。

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

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

入力

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

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

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

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

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

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

出力

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

入力例 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

出力例 1

4
5
2
1
3

入力例 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

出力例 2

3
2
5
1
4