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 tất cả các thao tác.

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\).

Example

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

0 7 3

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

3 3 0

Scoring

• \(30\%\) số test có ràng buộc bổ sung: tất cả thao tác chỉ liên quan đến cốc \(1\) và cốc \(2\) (\(u, v \in \{1, 2\}\)).
• \(30\%\) số test khác có ràng buộc bổ sung: \(N \le 100\).
• \(40\%\) số test còn lại không có ràng buộc bổ sung.