33048번 - 점봉은 무거워

문제

preview

마작 세트의 구성품 중 하나인 점봉^點棒은 각 플레이어의 점수를 나타내는 기다란 막대입니다. 마작 세트에는 다양한 종류의 점봉이 많이 들어 있습니다.

여러분은 마작 세트를 막 구입했습니다. 이 마작 세트는 특이해서, 다음과 같이 총 21ドル$종류의 점봉이 들어 있습니다.

• 100ドル,ドル 1ドル,000円,ドル 10ドル,000円,ドル $\dots,ドル 10ドル^{12}$점봉.
• 500ドル,ドル 5ドル,000円,ドル 50ドル,000円,ドル $\dots,ドル 5ドル \times 10^{11}$점봉.

마작을 치는 4ドル$명의 플레이어 1ドル,ドル 2ドル,ドル 3ドル,ドル 4ドル$는 같은 점봉 조합을 가지고 게임을 시작합니다.

게임을 플레이하다 보면, 점수를 교환할 일이 생깁니다. 플레이어들은 점수를 교환해야 할 때 점봉을 주고받습니다. 다만 이 마작 세트의 점봉은 상당히 무겁기 때문에, 플레이어들이 점봉을 주고받을 때 정해진 규칙에 따라 점봉을 주고받으려고 합니다.

만약 플레이어 $A$가 $B$에게 $X$점을 주어야 하는 상황이라고 합시다.

1. $A$가 $B$에게 준 점봉의 점수 합을 $S_A,ドル $B$가 $A$에게 준 점봉의 점수 합을 $S_B$라고 하면, $S_A - S_B = X$를 만족해야 합니다.
2. 1번 조건을 만족하는 점봉 교환 방법이 여러 개라면, $A$가 $B$에게 준 점봉의 개수를 $N_A,ドル B가 A에게 준 점봉의 개수를 $N_B$라고 했을 때, $N_A + N_B$가 그 중 최소가 되어야 합니다.
3. 1번과 2번 조건을 만족하는 점봉 교환 방법이 여러 개라면, $N_B$가 그 중 최소가 되어야 합니다.
4. 1번, 2번, 그리고 3번 조건을 만족하는 점봉 교환 방법이 여러 개라면, $S_B$가 그 중 최소가 되어야 합니다.

규칙에 따라 점봉을 주고받는 방법이 존재한다면 유일함을 증명할 수 있습니다. 방법이 유일하다는 것은, 두 개의 방법에 대해 어떤 $N$이 존재해 $N$점봉의 교환 개수가 달라지는 경우가 없음을 뜻합니다.

플레이어들의 마작 기록이 주어졌을 때, 각 점수 교환에 몇 개의 점봉이 오갔는지를 구해 주세요.

입력

첫 번째 줄과 두 번째 줄에는 각 점봉의 초기 개수를 의미하는 정수들이 공백으로 구분되어 주어집니다.

• 첫 번째 줄에는 $A_2, A_3, \dots, A_{12}$가 주어집니다. $A_i$는 한 플레이어의 초기 10ドル^i$점봉의 개수를 뜻합니다. $(0 \le A_i \le 10^6)$
• 두 번째 줄에는 $B_2, B_3, \dots, B_{11}$이 주어집니다. $B_i$는 한 플레이어의 초기 5ドル \times 10^i$점봉의 개수를 뜻합니다. $(0 \le B_i \le 10^6)$

세 번째 줄에는 게임을 하면서 일어난 점수 교환의 수 $Q$가 주어집니다. $(1 \le Q \le 10^5)$

다음 $Q$개의 줄에는 점수 교환들의 정보가 주어집니다.

• $Q$개의 줄 중 $i$번째 줄에는 $i$번째로 일어난 점수 교환의 정보를 의미하는 정수 $A,ドル $B,ドル $X$가 공백으로 구분되어 주어집니다. 이는 플레이어 $A$가 $B$에게 $X$점을 주어야 한다는 뜻입니다. $(1 \le A,B \le 4;$ $A\ne B;$ 100ドル \le X \le 9 \times 10^{18};$ $X \equiv 0 \pmod{100})$

규칙에 따라 점수를 교환할 경우 점봉을 주고받는 방법이 반드시 존재합니다. 각 점수 교환은 플레이어들이 가지고 있는 점봉의 개수를 바꾼다는 점에 유의합니다.

출력

$Q$줄을 출력합니다. $i$번째 줄에는 $i$번째 점수 교환에서 오간 점봉의 개수를 출력합니다. 구체적으로는, $N_A+N_B$를 출력합니다.

제한

힌트