Bạn có ba chiếc cốc có dung tích lần lượt là ~A, B~ và ~C~ lít. Ban đầu, cốc 1 chứa đầy nước (~A~ lít), cốc 2 và cốc 3 đều rỗng.

Bạn được cho một danh sách gồm ~N~ thao tác. Mỗi thao tác có dạng ~u~ ~v~ (~1 \le u, v \le 3, u \neq v~), nghĩa là rót nước từ cốc ~u~ sang cốc ~v~. Khi rót, bạn rót cho đến khi cốc ~u~ hết nước hoặc cốc ~v~ đầy, tùy điều kiện nào xảy ra trước.

Hãy in ra lượng nước trong ba cốc sau khi thực hiện xong.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~A, B, C~ (~1 \le A, B, C \le 10^9~) — dung tích của ba cốc.

• Dòng thứ hai chứa một số nguyên dương ~N~ (~1 \le N \le 10^5~) — số lượng thao tác.

• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ (~1 \le u, v \le 3, u \neq v~).

Output

In ra ba số nguyên trên một dòng, cách nhau bởi dấu cách: lượng nước trong cốc 1, cốc 2 và cốc 3.

Scoring

Sample Input 1

10 7 3
5
1 2
2 3
3 1
2 3
1 2

Sample Output 1

0 7 3

Sample Input 2

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

Sample Output 2

3 3 0

Notes

Test 1:

• Ban đầu: (10, 0, 0)

• 1 ~\rightarrow~ 2: (3, 7, 0)

• 2 ~\rightarrow~ 3: (3, 4, 3)

• 3 ~\rightarrow~ 1: (6, 4, 0)

• 2 ~\rightarrow~ 3: (6, 1, 3)

• 1 ~\rightarrow~ 2: (0, 7, 3)

Test 2:

• Ban đầu: (6, 0, 0)

• 1 ~\rightarrow~ 2: (2, 4, 0)

• 2 ~\rightarrow~ 3: (2, 1, 3)

• 1 ~\rightarrow~ 2: (0, 3, 3)

• 2 ~\rightarrow~ 3: (0, 3, 3) — không đổi

• 3 ~\rightarrow~ 1: (3, 3, 0)