Robot thám hiểm sao Hỏa đang ở điểm có tọa độ \((0,0)\) nhận được dòng lệnh điều khiển từ Trái đất. Dòng lệnh chỉ chứa các kí tự thuộc tập kí tự \(\{E, S, W, N\}\), mỗi kí tự là một lệnh di chuyển với quãng đường bằng một đơn vị độ dài:

• E: di chuyển về hướng Đông, tức là nếu robot đang ở tọa độ \((x,y)\) thì sau khi thực hiện lệnh E robot sẽ ở tọa độ \((x+1,y)\).
• S: di chuyển về hướng Nam, tức là nếu robot đang ở tọa độ \((x,y)\) thì sau khi thực hiện lệnh S robot sẽ ở tọa độ \((x,y-1)\).
• W: di chuyển về hướng Tây, tức là nếu robot đang ở tọa độ \((x,y)\) thì sau khi thực hiện lệnh W robot sẽ ở tọa độ \((x-1,y)\).
• N: di chuyển về hướng Bắc, tức là nếu robot đang ở tọa độ \((x,y)\) thì sau khi thực hiện lệnh N robot sẽ ở tọa độ \((x,y+1)\).

Hãy xác định tọa độ của robot sau khi thực hiện hết dòng lệnh di chuyển.

Input

• Gồm một dòng chứa xâu \(s\) mô tả dãy lệnh, các kí tự của \(s\) là các chữ cái in hoa và thuộc tập kí tự \(\{E,S,W,N\}\).
• Độ dài của \(s\) thuộc đoạn từ 1 đến \(10^5\).

Output

• Ghi ra hai số nguyên tương ứng là hoành độ \(x\) và tung độ \(y\) của robot sau khi thực hiện lệnh di chuyển.

Giới hạn

• Có 30% số test tương ứng với 30% số điểm thỏa mãn: độ dài của xâu \(s\) không vượt quá 100.
• Có 30% số test tương ứng với 30% số điểm thỏa mãn: tất cả các kí tự của xâu \(s\) đều giống nhau (tức là tất cả các kí tự của xâu \(s\) đều là E hoặc S hoặc W hoặc N).
• Có 40% số test còn lại với 40% số điểm không có thêm ràng buộc nào.

Ví dụ

ENENWWWS

-1 1

An và Chi đang chơi một trò chơi đoán số như sau:
An nghĩ ra 4 số nguyên dương; số đầu tiên anh ta chọn là một số nguyên dương bất kì, mỗi số tiếp theo bằng số trước đó cộng với cùng một hằng số dương nào đó. Sau đó An đưa cho Chi một mảnh giấy mà anh ta đã viết 3 số được chọn ngẫu nhiên trong 4 số. Chi sẽ thắng nếu đoán đúng số còn thiếu. Hãy giúp Chi tìm các số có thể là số còn thiếu.

Một số có thể là số còn thiếu nếu nó là số nguyên dương và nó cộng với 3 số ghi trên mảnh giấy có thể sắp xếp theo một thứ tự nào đó sao cho mỗi số kế từ số thứ hai trở đi, bằng số liền kề trước đó cộng với cùng một hằng số dương nào đó.

Yêu cầu: Cho ba số nguyên dương \(a,b,c\) (\(1 \le a,b,c \le 10^9\)) là ba số được ghi trên mảnh giấy mà An đưa cho Chi. Dữ liệu vào đảm bảo rằng số còn thiếu luôn tồn tại. Hãy liệt kê các số có thể là số còn thiếu, theo thứ tự tăng dần.

Input

• Một dòng chứa ba số nguyên dương \(a, b, c\) (\(1 \le a,b,c \le 10^9\)), cách nhau một khoảng trắng.

Output

• Ghi ra một dòng chứa các số có thể là số còn thiếu, theo thứ tự tăng dần, cách nhau một khoảng trắng.

Giới hạn

• 30% số test ứng với 30% số điểm thỏa mãn \(b - a = c - b > 0\).
• 30% số test khác ứng với 30% số điểm thỏa mãn \(1 \le a,b,c \le 10^9\).
• 40% số test còn lại với 40% số điểm không có thêm ràng buộc nào.

4 6 8

2 10

Để chuẩn bị cho một cuộc thi quan trọng trong năm, An đã học cách tính số ước của một số và nhanh chóng hiểu được các thuật toán khác nhau. Sau đó, trong quá trình tự luyện tập, An quyết định tìm hiểu mối quan hệ giữa một số và số ước của nó.

Cho hai số nguyên dương \(n\) và \(k\), hãy tính số cặp nguyên dương \((x,y)\) với \(1 \le x \le y \le n\) mà thỏa mãn:
\( k \times d(x) \times d(y) = x \times y \)
trong đó \(d(x), d(y)\) lần lượt là số ước nguyên dương của \(x\) và \(y\).

Input

Một dòng chứa hai số nguyên tố dương \(n\) và \(k\) \((1 \le n \le 3\times10^5,\,1 \le k \le 10^9)\).

Output

Ghi ra một số nguyên là số cặp \((x, y)\) thỏa mãn điều kiện trên.

Giới hạn

• 20% số test ứng với \(1 \le n \le 100\).
• 20% số test ứng với \(1 \le n \le 600\).
• 20% số test ứng với \(1 \le n \le 4000\).
• 20% số test ứng với \(1 \le n \le 10^4\).
• 20% số test còn lại không có thêm ràng buộc.

Ví dụ

8 3

2

25 9

6

Gần đây nhóm bạn An đã khám phá ra một kho báu trên hòn đảo hoang. Trên cánh cửa lối vào, An có ghi một xâu nhị phân \(s\) (xâu chỉ chứa các chữ số 0 và 1). Khi thử \(s\) là độ dài của xâu, tức là số kí tự của xâu \(s\). Các kí tự của xâu \(s\) được đánh chỉ số từ 1 đến \(\lvert s\rvert\).

Sau khi nghiên cứu tài liệu và bàn thảo, An đã biết được mật mã để mở cửa kho báu này là một bộ 4 số \(\ell_1, r_1, \ell_2, r_2\) trong dãy \([1,\lvert s\rvert]\) hai đoạn con khác nhau của xâu \(s\). Hai đoạn này phải cùng độ dài và là hai đoạn con không trùng nhau, hơn nữa tổng chữ số của hai đoạn này phải bằng nhau. Cụ thể, mật mã của kho báu là 4 số \(\ell_1, r_1, \ell_2, r_2\) sao cho:

• \(1 \le \ell_1 \le \lvert s\rvert\) và \(1 \le \ell_2 \le \lvert s\rvert\), \( \ell_1 \neq \ell_2\).
• \([\,\ell_1, r_1]\) và \([\,\ell_2, r_2]\) là hai đoạn khác nhau của \(s\) tức là \(\ell_1 \neq \ell_2\) và \(r_1 \neq r_2\).
• \(r_1 - \ell_1 = r_2 - \ell_2\) (cùng độ dài).
• Tổng số chữ số 1 trong xâu con \(s_{\ell_1..r_1}\) bằng tổng số chữ số 1 trong \(s_{\ell_2..r_2}\).
• Độ dài \((r_1 - \ell_1 + 1)\) là lớn nhất có thể.

Theo như An tìm hiểu từ bàn thảo nếu có nhiều bộ 4 thỏa thì bất kì bộ nào trong chúng đều có thể làm mật mã. Bây giờ An cần mật mã cho kho báu, nhưng anh ấy không thể tìm được nếu không có sự giúp đỡ của bạn. Bạn hãy giúp An tìm mật mã của kho báu.

Input

• Dòng đầu tiên chứa số nguyên \(t\) \((1 \le t \le 5)\) là số test.
• Mỗi test gồm một dòng chứa xâu nhị phân \(s\) (xâu chỉ bao gồm ký tự 0 và 1), độ dài \(1 \le \lvert s\rvert \le 10^6\).

Output

Với mỗi test in kết quả trên một dòng:

• Nếu tồn tại một bộ \(\ell_1, r_1, \ell_2, r_2\) sao cho các điều kiện trên đều thỏa, in ra bốn số ℓ1 r1 ℓ2 r2 là mật mã có độ dài đoạn lớn nhất (nếu có nhiều đáp án hãy in bất kì một bộ nào).
• Nếu không tồn tại, in ra -1.

Giới hạn

• 25% số test: tổng độ dài tất cả các xâu \(s\) không vượt quá 50.
• 25% số test: tổng độ dài tất cả các xâu \(s\) không vượt quá 500.
• 25% số test: tổng độ dài tất cả các xâu \(s\) không vượt quá \(10^4\).
• 25% số test còn lại: tổng độ dài tất cả các xâu \(s\) không vượt quá \(10^6\).

Ví dụ

3
111111
010101
1

1 5 2 6
2 5 3 6
-1