Trò chơi Bang! là board game quá quen thuộc đối với nhóm bạn của Nhật. Trong ván đấu sẽ có \(3\) phe: cảnh sát, kẻ cướp và kẻ phản bội. Mục tiêu của cảnh sát là giết hết kẻ cướp và phản bội, mục tiêu của kẻ cướp là giết cảnh sát trưởng, còn của kẻ phản bội là người sống sót cuối cùng.

Mỗi người chơi đều có những lá bài để chiến đấu, và lá Bang! là lá tấn công cơ bản. Trong đó, lá bài Đấu súng có lẽ là lá bài khiến lá Bang! trở nên mạnh nhất.
Giả sử người chơi A ra lá Đấu súng để thách đấu người chơi B, hai người sẽ lần lượt đấu súng như sau:

• Đầu tiên, nếu B không có lá Bang!, B thua và cuộc đấu súng dừng ngay lập tức. Ngược lại, người B sẽ phải đưa ra một lá Bang!
• Tiếp theo, nếu A không có là Bang!, A thua và cuộc đấu súng dừng ngay lập tức. Ngược lại, người A sẽ phải đưa ra một lá Bang!
• Tương tự cuộc đấu súng tiếp tục tới lượt của B, A, B, A, ... cho tới khi một trong hai người chơi không thể đưa ra lá Bang!.

Bàn chơi hiện tại có \(n\) người chơi, với người chơi thứ \(i\) có \(a_i\) lá Bang!. Có \(T\) sự kiện, mỗi sự kiện gồm hai số \(u, v\), đại diện cho việc người chơi thứ \(u\) thách đấu người chơi thứ \(v\). Hai người sẽ đấu theo đúng quy tắc luân phiên như trên tới khi một trong hai không còn lá Bang! để ra.

Hỏi sau \(T\) sự kiện, mỗi người chơi còn bao nhiêu lá Bang! trong tay?

Chú ý: Việc thua trong cuộc đấu Đấu súng chỉ ảnh hưởng tới việc tiêu hao lá Bang! trong tay; kết quả mạng sống (thua, thắng) không ảnh hưởng đến lượt chơi tiếp theo và mọi người chơi đều tiếp tục tham gia đầy đủ các sự kiện.

Input

• Dòng đầu tiên chứa số tự nhiên \(n\) \((1 \leq n \leq 2 \times 10^5)\).
• Dòng thứ hai chứa dãy số tự nhiên \(a\) \((1 \leq a_i \leq 10^9)\) gồm \(n\) phần tử cách nhau bằng dấu cách.
• Dòng thứ ba số \(T\) \((1 \leq t \leq 2 \times 10^5)\).
• \(T\) dòng tiếp theo, dòng thứ \(i\) gồm hai số \(u_i, v_i\).

Output

• In ra một dòng là dãy số tự nhiên \(a\).

Scoring

• \(50\%\) số điểm có \(t \leq 1000\) và \(a_i \leq 100\).
• \(50\%\) số điểm không có rằng buộc gì thêm.

Example

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

0 0 0 1 3