23822번 - Black Friday 스페셜 저지

문제

$n$명의 게이머들이 블랙 프라이데이를 맞아 매장에 몰려왔습니다! 매장에는 총 $m$종류의 게임과 $k$종류의 게임기가 존재합니다. 매장을 열기 전, $i$번째 게임은 총 $a_i$개가 존재하며, $i$번째 게임기는 $b_i$개가 존재합니다. $j$번째 게이머는 $c_j$번 게임 혹은 $d_j$번 게임기중 하나를 구매하려고 합니다. 만약, 아무것도 구매하지 못한다면, 그 게이머는 매우 화가 나 매장을 혼란스럽게 만들 수 있습니다.

당신은 이 매장의 매니저가 되었습니다. 당신은 각 게이머들에게 게임을 사게하거나, 게임기를 사게하거나, 돌려보내게 할 수 있습니다. 블랙 프라이데이에 게임 혹은 게임기를 구매하는 고객이 최대한 많아지도록 해야합니다.

입력

첫 번째 줄에 $n, m, k$가 주어집니다. (1ドル \leq n \leq 2,000,000, 1 \leq m,k \leq 2,000$)

두 번째 줄에 $a_1, a_2, … , a_m$이 주어집니다. (1ドル \leq a_i \leq 10^9$)

세 번째 줄에 $b_1, b_2, … , b_k$가 주어집니다. (1ドル \leq b_i \leq 10^9$)

네 번째 줄부터 $n$개의 줄에 걸쳐 $c_j, d_j$가 주어집니다. (1ドル \leq c_j \leq m, 1\leq d_j \leq k$)

출력

첫 번째 줄에 게임 혹은 게임기를 구매한 고객수의 최댓값을 출력합니다.

두 번째 줄부터 $n$개의 줄에 걸쳐 $e_i ,円 (e_i = 0, 1, 2)$를 출력해야합니다.

구매한 고객수가 최대인 경우에 대하여, $i$번째 고객을 돌려보냈으면 $e_i=0,ドル 게임을 구매하게 하였으면 $e_i=1,ドル 게임기를 구매하게 하였으면 $e_i=2$입니다.

만약 구매한 고객수가 최대가 되는 경우가 여러 개 존재한다면, 아무거나 출력하면 됩니다.

제한

힌트