Trong câu lạc bộ nghệ thuật của trường, đạo diễn đang dàn dựng một tiết mục đôi mang tên Vòng Xoay. Điểm nhấn của tiết mục là một dải lụa sân khấu có độ dài đúng bằng \(1\) mét, được buộc vào tay của cả hai người và luôn được giữ căng trong suốt màn biểu diễn để tạo nên các đường chuyển động mềm mại, chính xác.

Biên đạo của tiết mục quy định rằng tại mọi thời điểm luôn có đúng một người giữ vai trò người trụ, còn người kia là người xoay hoạt động như sau:

• Người trụ đứng yên tại chỗ để giữ điểm tựa cho động tác.
• Người xoay chuyển động liên tục theo chiều kim đồng hồ quanh người trụ với tốc độ góc \(90^\circ\) mỗi giây.
• Vì dải lụa luôn căng và có độ dài đúng bằng \(1\) mét, khoảng cách giữa hai người luôn bằng \(1\) mét tại mọi thời điểm.

Việt và Hàn là hai diễn viên chính của buổi biểu diễn. Trên mặt phẳng tọa độ, ban đầu Việt đứng tại \((0, 0)\) còn Hàn đứng tại \((1, 0)\). Khi màn biểu diễn bắt đầu, Việt là người xoay, còn Hàn là người trụ.

Để tiết mục trở nên hấp dẫn hơn, đạo diễn chèn vào kịch bản một số thời điểm đổi vai. Tại một thời điểm đổi vai:

• Người đang là người xoay lập tức trở thành người trụ.
• Người đang là người trụ lập tức trở thành người xoay.

Việc đổi vai diễn ra tức thời và không tốn thời gian. Toàn bộ tiết mục kéo dài đúng \(T\) giây.

Quá trình hoàn thiện tiết mục diễn ra qua \(N\) buổi tập. Ở buổi tập thứ \(i\), đạo diễn bổ sung thêm đúng một mốc đổi vai mới vào kịch bản như sau:

• Ở buổi tập thứ \(1\), kịch bản có một lần đổi vai tại thời điểm \(b_1\).
• Ở buổi tập thứ \(2\), kịch bản có các lần đổi vai tại các thời điểm \(b_1, b_2\).
• ...
• Ở buổi tập thứ \(i\), kịch bản có các lần đổi vai tại các thời điểm \(b_1, b_2, \dots, b_i\).

Lưu ý

• Trong mỗi buổi tập, các thời điểm đổi vai là đôi một khác nhau.
• Dãy \(b_1, b_2, \dots, b_N\) trong input biểu diễn thứ tự các mốc được thêm vào qua từng buổi tập mà không phải thứ tự thời gian xuất hiện trên sân khấu. Vì vậy, trong trường hợp tổng quát, không đảm bảo là \(b_1 < b_2 < \dots < b_N\).
• Nếu có một lần đổi vai tại thời điểm \(t\), thì việc đổi vai xảy ra đúng tại thời điểm đó.
• Nói cách khác, chuyển động trong khoảng thời gian từ \(k - 1\) đến \(k\) vẫn sử dụng vai trò trước khi đổi; còn chuyển động sau thời điểm \(k\) sử dụng vai trò sau khi đổi.
• Ví dụ, nếu trong \(3\) giây đầu không có lần đổi vai nào, thì vị trí của Việt lần lượt sau \(1, 2, 3\) giây là \((1, 1), (2, 0), (1, -1)\).

Yêu cầu

Với mỗi buổi tập, hãy xác định tọa độ cuối cùng của Việt sau đúng \(T\) giây nếu biểu diễn theo kịch bản của buổi tập đó.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(T\) (\(1 \le N \le 10^5, N + 1 \le T \le 5 \cdot 10^5\)).
• Dòng thứ \(i\) trong số \(N\) dòng tiếp theo chứa một số nguyên \(b_i\) (\(1 \le b_i \le T - 1\)).

Output

• Ghi ra \(N\) dòng: Dòng thứ \(i\), in hai số nguyên \(x\) và \(y\) là tọa độ của Việt sau đúng \(T\) giây trong kịch bản của buổi tập thứ \(i\).

Example

2 6
3
2

1 -1
3 1

Subtask

• Subtask \(1\) (20 điểm): \(N \le 2000, T \le 2000\).
• Subtask \(2\) (20 điểm): \(b_1 < b_2 < \dots < b_N\).
• Subtask \(3\) (30 điểm): \(T \le 5 \cdot 10^4\).
• Subtask \(4\) (30 điểm): Không có ràng buộc nào thêm.