Hãy xem xét ~G~ là một đồ thị có hướng không chu trình. Nếu ~c_1, c_2, c_3, ..., c_n~ là các đỉnh phân biệt của ~G~ sao cho tồn tại một đường đi từ ~c_1~ đến ~c_2~, từ ~c_2~ đến ~c_3~, ..., và từ ~c_{n−1}~ đến ~c_n~, ta nói rằng mảng ~C~ ~=~ ~(c_1, c_2, c_3, ..., c_n)~ là một mảng có thứ tự bắt đầu từ ~c_1~ và kết thúc tại ~c_n~. Lưu ý rằng giữa các phần tử liền kề ~c_i~ và ~c_{i+1}~ của mảng có thứ tự ~C~ không nhất thiết phải có một cạnh trực tiếp, chỉ cần có đường đi tồn tại từ ~c_i~ đến ~c_{i+1}.

Đối với định nghĩa này của mảng có thứ tự ~C =~ ~(c_1, c_2, c_3, ..., c_n)~, chúng ta định nghĩa độ dài của nó là ~len(C) = n~. Do đó, độ dài của một mảng có thứ tự bằng với số đỉnh mà nó chứa. Lưu ý rằng mảng có thứ tự có thể có độ dài là ~1~ khi chỉ chứa một đỉnh, đại diện cho cả điểm bắt đầu và kết thúc của nó.

Ngoài ra, đối với một mảng có thứ tự ~C =~ ~(c_1, c_2, c_3, ..., c_n)~ chúng ta có thể định nghĩa dấu của nó là ~sgn(C) = (−1)^{len(C)+1}~. Đối với các đỉnh ~x~ và ~y~ của ~G~, hãy ký hiệu ~S_{x,y}~ là tập hợp tất cả các mảng có thứ tự bắt đầu tại ~x~ và kết thúc tại ~y~.

Cuối cùng, chúng ta định nghĩa sức căng giữa hai nút ~x~ và ~y~ là ~tns(x, y) = \Sigma_{C \in S_{x, y}} sgn(C)~. Do đó, sức căng giữa hai nút ~x~ và ~y~ bằng tổng các dấu của tất cả các mảng có thứ tự bắt đầu từ ~x~ và kết thúc tại ~y~.

Một số nguyên ~K~ được cho. Nhiệm vụ của bạn là xây dựng một đồ thị có hướng không chu trình với tối đa ~1000~ đỉnh và tối đa ~1000~ cạnh sao cho ~tns(1, N) = K~. Số ~N~ trong biểu thức trước đây chỉ số đỉnh trong đồ thị. Các đỉnh của đồ thị nên được đánh chỉ số bằng các số nguyên dương từ ~1~ đến ~N~.

Input

Dòng đầu tiên chứa một số nguyên ~K~ ~(|K| \leq 10^{18})~ từ mô tả bài toán.

Output

• Trong dòng đầu tiên, bạn nên xuất ra số lượng đỉnh và số lượng cạnh của đồ thị đã được xây dựng. Hãy ký hiệu số lượng đỉnh của đồ thị đó là ~N~ ~(1 \leq N \leq 1000)~, và số lượng cạnh là ~M~ ~(0 \leq M \leq 1000)~.
• Trong ~M~ dòng tiếp theo, bạn nên xuất ra hai số nguyên phân biệt ~X_i~ và ~Y_i~ ~(1 \leq X_i, Y_i \leq N)~, đại diện cho cạnh thứ ~i~ được hướng từ đỉnh có chỉ số ~X_i~ đến đỉnh có chỉ số ~Y_i~. Mỗi cạnh chỉ xuất hiện một lần trong đầu ra.

Ngoài ra, giá trị tuyệt đối của sức căng giữa mỗi cặp nút trong đồ thị phải nhỏ hơn hoặc bằng ~2^{80}~.

Nếu có nhiều giải pháp, xuất bất kỳ giải pháp nào.

Chú ý

• Subtask 1: 15 điểm ~1 \leq K < 500~.
• Subtask 2: 15 điểm ~−300 < K \leq 1~.
• Subtask 3: 20 điểm ~|K| < 10000~.
• Subtask 4: 60 điểm Không có ràng buộc bổ sung.

Sample Input 1

0

Sample Ouput 1

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

Sample Input 2

1

Sample Ouput 2

1 0

Sample Input 3

2

Sample Ouput 3

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

Giải thích

Trong test đầu tiên Đồ thị được xây dựng có 6 đỉnh. Các mảng có thứ tự bắt đầu từ 1 và kết thúc tại 6 là: (1, 6), (1, 4, 6), (1, 5, 6), (1, 3, 6), (1, 2, 6), (1, 4, 3, 6), (1, 4, 2, 6), (1, 5, 3, 6), (1, 5, 2, 6), (1, 3, 2, 6), (1, 4, 3, 2, 6), (1, 5, 3, 2, 6). Độ dài của chúng lần lượt là: 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, vì vậy dấu của chúng lần lượt là −1, 1, 1, 1, 1, −1, −1, −1, −1, −1, 1, 1. Do đó, sự căng thẳng giữa 1 và 6 bằng 0.