Welcome Contest (京都・オープン) 2026/03/26 14:00 ~ 2026/03/26 18:00 4:00:00.000

D Area 01

問題
制限時間: 2 sec メモリ制限: 1024 MB
Area 01
Statement

以下をすべて満たす正整数の組 \((a, b, c, d)\) を \(2 \times 10^5\) 種類出力してください。

  • \(1 \leq a,b,c,d\)
  • \(a \leq b\)
  • \(c \leq d\)
  • \(ab - cd = 1\)

出力された値の最大値を \(M\) とします。\(M\) によって以下の得点を得ることができます。

  • \(10^9 \lt M\): 0 点
  • \(3 \times 10^5 \lt M \leq 10^9\): 5 点
  • \(10^3 \lt M \leq 3 \times 10^5\): 10 点
  • \(M \leq 10^3\): 100 点

Input

入力は与えられません。

Output

\(2\times 10^5\) 行出力して下さい。\(\\ \) \(i\) 行目に \(i\) 個目の \((a,b,c,d)\) の組を、以下の形式で出力してください。

\(a~b~c~d\)

出力される \((a,b,c,d)\) の組は相異なる必要があります。

Scoring

出力された値の最大値を \(M\) とします。\(M\) によって以下の得点が与えられます。

  • \(10^9 \lt M\): 0 点
  • \(3 \times 10^5 \lt M \leq 10^9\): 5 点
  • \(10^3 \lt M \leq 3 \times 10^5\): 10 点
  • \(M \leq 10^3\): 100 点

この問題では、獲得した点数が最後に増加した時刻を回答時間とします。

Example

Input 1
 
Output 1
8 8 7 9
3 26 7 11

Note

出力例は \((a,b,c,d) = (8,8,7,9), (3,26,7,11)\) の \(2\) つを出力しています。 出力される \((a,b,c,d)\) の組の個数が足りないので、この出力は不正解となります。