Nena azt álmodta, hogy a csillagos eget bámulja. Az eget kétdimenziós síknak tekinthetjük, amelyben a csillagok pontokként szerepelnek. Amikor Nena felébredt, rájött, hogy késésben van, és hogy álmából szinte semmire sem emlékszik. Csak a \(K\) számra emlékezett, a kollineáris pont hármasok számára. Ha a csillagokat az \(A_1, A_2, \ldots, A_N\) egymástól különböző pontok képviselik, akkor a kollineáris pont hármasok száma valójában azon \((i,j,k)\) rendezett hármasok számával azonos, amelyekre érvényes, hogy \(1 \leq i < j < k \leq N\) és az \(A_i, A_j, A_k\) pontok kollineárisak.

Segítsetek Nenának úgy, hogy létrehoztok neki egy legfeljebb \(2000\) különböző pontot tartalmazó halmazt, amelyre érvényes, hogy pontosan \(K\) számú kollineáris pont hármast tartalmaz. Nena szereti az egész számokat, de nem szereti azokat, amelyek abszolút értéke nagyobb, mint \(10^9\), ezért az általatok létrehozott halmazban lévő pontok koordinátáinak e feltételeknek eleget kell tenni. Nem feltétel a pontok számának minimalizálása. Biztosak vagyunk abban, hogy az adott feltételek mellett legalább egy megoldás létezik.

Bemenet

A szabványos bemenet első és egyetlen sorában a \(K\) egész szám, a keresett kollineáris pont hármasok száma áll.

Kimenet

A szabványos kimenet első sorában kiíratni az \(N\) természetes számot, a pontok számát. A következő \(N\) sorban pedig kiíratni az \(x_i, y_i\) egész számokat, az \(A_i\) pontok koordinátáit. Ezekre a számokra érvényes kell hogy legyen \(-10^9 \leq x_i, y_i \leq 10^9\). Minden kiírt pontnak különbözőnek kell lenni a többitől.

1. példa

Bemenet

8

Kimenet

9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

2. példa

Bemenet

2

Kimenet

5
0 2
0 1
0 0
1 0
2 0

3. példa

Bemenet

4

Kimenet

4
0 0
1 1
2 2
3 3

A példák magyarázata

• Az első példában a pontok egy \(3 \times 3\) formátumú négyzethálót alkotnak. Soronként és oszloponként is 3-3 kollineáris hármast alkotnak, valamint átlósan 2 kollineáris hármas is megjelenik. Összesen 8 kollineáris hármast alakíthatunk ki.
• A második példában az első három és az utolsó három pont alakít ki 1-1 kollineáris hármast.
• A harmadik példában minden hármas kollineáris. Összesen 4 ilyen van.

Korlátozások

• \(1 \leq K \leq 10^8\)

A tesztpéldák 4 független csoportba oszthatók:

• Tesztpéldák, melyek 20 pontot érnek: \(K \le 10\).
• Tesztpéldák, melyek 20 pontot érnek: \(K \leq 2000\).
• Tesztpéldák, melyek 20 pontot érnek: \(K \leq 10^6\).
• Tesztpéldák, melyek 40 pontot érnek: nincs külön korlátozás.