Konstrukcija

Έστω ~G~ ένα κατευθυνόμενο άκυκλο γράφημα. Αν ~c_1,\;c_2,\;c_3,\;\ldots~, οι ~c_n~ είναι διακριτοί κόμβοι του ~G~ έτσι ώστε να υπάρχει ακμή από το ~c_1~ στο ~c_2~, από το ~c_2~ στο ~c_3,\;\ldots~ και από το ~c_{n-1}~ στο ~c_n~. Λέμε ότι αυτός ο πίνακας ~C\;=\;(c_1,\;c_2,\;c_3,\;\ldots,\;c_n)~ είναι ένας διατεταγμένος πίνακας που ξεκινά από το ~c_1~ και τελειώνει στο ~c_n~. Σημειώστε ότι μεταξύ γειτονικών στοιχείων ~c_i~ και ~c_i + 1~ του διατεταγμένου πίνακα ~C~ δεν είναι απαραίτητο να υπάρχει άμεση ακμή.

Για αυτόν τον ορισμό ενός διατεταγμένου πίνακα ~C\;=\;(c_1,\;c_2,\;c_3,\;\ldots,\;c_n)~, ορίζουμε το μήκος του ~len(C) = n~. Επομένως, το μήκος ενός διατεταγμένου πίνακα είναι ίσο με τον αριθμό των κόμβων που έχει. Σημειώστε ότι ο διατεταγμένος πίνακας μπορεί έχει μήκος 1 όταν κρατάμε έναν μόνο κόμβο που αντιπροσωπεύει και την αρχή και το τέλος του.

Επίσης, για έναν διατεταγμένο πίνακα ~C\;=\;(c_1,\;c_2,\;c_3,\;\ldots,\;c_n)~ μπορούμε να ορίσουμε το πρόσημο του ως ~sgn(C) = (-1)^{len(C)+1}~. Για κόμβους ~x~ και ~y~ του ~G~, ας συμβολίσουμε με ~S{x,y}~ ένα σύνολο από όλους τους διατεταγμένους πίνακες που ξεκινούν με ~x~ και τελειώνουν σε ~y~.

Τέλος, ορίζουμε την τάση μεταξύ των κόμβων ~x~ και ~y~ ως ~tns(x,y) = \sum~~_C~~_\in~~_S~~_{x,y}~~sgn(C)~. Επομένως, η τάση μεταξύ των κόμβων ~x~ και ~y~ ισούται με το άθροισμα των προσημάτων όλων των διατεταγμένων πινάκων που ξεκινούν σε ~x~ και τελειώνουν σε ~y~.

Δίνεται ακέραιος ~K~. Σκοπός σας είναι να κατασκευάσετε ένα κατευθυνόμενο άκυκλο γράφημα με το πολύ ~1000~ κόμβους και το πολύ ~1000~ ακμές για τις οποίες ισχύει ~tns(1,N) = K~. Ο αριθμός ~N~ στην προηγούμενη έκφραση υποδηλώνει τον αριθμό των κόμβων σε ένα γράφημα. Οι κόμβοι ενός γραφήματος πρέπει να ευρετηριάζονται χρησιμοποιώντας θετικούς ακέραιους αριθμούς από το 1 έως το ~N~.

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό ~K\;(|K| \le 10{18})~.

Έξοδος

Στην πρώτη γραμμή θα πρέπει να τυπώσετε τον αριθμό των κόμβων και τον αριθμό των ακμών του κατασκευασμένου γραφήματος. Ας υποδηλώσουμε τον αριθμό των κόμβων αυτού του γραφήματος με ~N\;(1 \le N \le 1000)~ και τον αριθμό των ακμών με ~M\;(0 \le M \le 1000)~.

Στην i-οστή των επόμενων ~M~ γραμμών θα πρέπει να εξάγετε δύο διακριτούς ακέραιους ~X_i~ και ~Y_i\;(1 \le X_i, Y_i \le N)~, οι οποίοι αντιπροσωπεύουν την i-οστή ακμή που κατευθύνεται από τον κόμβο με δείκτη ~X_i~ προς τον κόμβο με δείκτη ~Y_i~. Κάθε κόμβος εμφανίζεται μόνο μία φορά στην έξοδο.

Επίσης ή απόλυτη τιμή της τάσης μεταξύ δύο κόμβων στο γράφημα θα πρέπει να είναι μικρότερη ίση του ~2^{80}~.

Υπάρχουν πολλαπλές λύσεις, άρα τυπώστε οποιαδήποτε από αυτές.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	15	~1 \le K < 500~
2	15	~-300 < K \le 1~
3	20	~|K| < 10\,000~
4	60	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

0

output

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

Επεξήγηση του 1ου παραδείγματος:

Το κατασκευασμένο γράφημα έχει 6 κόμβους. Διατεταγμένα διανύσματα που ξεκινούν με 1 και τελειώνουν με 6 είναι:\((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). Τα μήκη τους (διατεταγμένα): \)1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4\(, άρα τα πρόσημα τους είναι \)-1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1\(. Επομένως, η τάση ανάμεσα στο 1 και στο 6 είναι \)-1 + 1 + 1 + 1 + 1 - 1 - 1 - 1 - 1 - 1 + 1 + 1 = 0~.

input

1

output

1 0

input

2

output

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