Cho một không gian bị phong ấn hình vuông được chia thành ~n*n~ ô, các hàng được đánh số từ ~1~ tới ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ tới ~n~ từ trái sang phải.

Ban đầu Rotund đang đứng ở vị trị ~[x,y]~.

Không gian phong ấn này có một đặc diểm, là mỗi khi di chuyển tới "tường" của không gian, bạn sẽ xuất hiện ở vị trí đối diện (bạn biết trò chơi rắn săn mồi không? Cơ chế nó sẽ giống như vậy đấy). Nếu đi theo đường chéo, bạn sẽ xuất hiện ở vị trí tương ứng trên cùng đường chéo đó.

Ví dụ: Nếu không gian có kích cỡ ~4*4~, Rotund đang đứng ở ô ~[2, 3]~ và đi 3 bước lên phía trên, thì cậu sẽ xuất hiện ở ô ~[3, 3]~ (3 bước màu xanh dương), còn đi chéo 2 bước xuống phía dưới bên phải thì sẽ xuất hiện tại ô ~[1, 2]~ (2 bước màu xanh lục).

~8~ hướng dược quy định như sau:

Cho ~q~ chỉ dẫn có dạng ~d~ ~k~, với ~d~ là hướng theo quy tắc, còn ~k~ là số bước di chuyển.

Rotund sẽ thực hiện lần lượt từng chỉ dẫn để tìm ra lỗ hổng trên cơ chế phong ấn của không gian (kết thúc của chỉ dẫn trước là xuất phát của chỉ dẫn sau).

Yêu cầu

Tìm ra vị trí của Rotund sau mỗi chỉ dẫn.

Input

• Dòng đầu tiên chứa 4 số nguyên dương ~n~, ~q~, ~x~, ~y~ ~(1≤x,y,n≤10^{18}~ | ~1≤q≤5*10^5~ | ~x,y≤n)~ cách nhau một dấu cách.
• ~q~ dòng sau, mỗi dòng là một chỉ dẫn có dạng ~d~, ~k~ ~(1≤d≤8~ | ~1≤k≤10^{18})~cách nhau một dấu cách.

Output

Gồm ~q~ dòng, mỗi dòng hai số nguyên dương là vị trí của Rotund sau từng chỉ dẫn.

Sample Input

4 3 2 3
1 3
3 1
4 2

Sample Output

3 3
3 4
2 3

Subtask

• Có 50% số test ứng với 50% số điểm có tổng số bước di chuyển của tất cả chỉ dẫn không vượt quá ~5*10^5~;
• 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.