配点 : $500$ 点

問題文

あなたは「AtCoderじゃんけん」という一対一のゲームの大会を主催することになりました。 大会の参加者は $N$ 人で、それぞれには $1$ から $N$ の相異なる番号が割り振られています。 アリーナには二人が入ることのできる対戦場が $M$ 個用意されており、あなたはそれぞれの対戦場に二つの相異なる $1$ 以上 $N$ 以下の整数を割り当てなければいけません。 複数の対戦場に同じ整数を割り当てることはできません。 大会は $N$ ラウンドによって構成され、それぞれのラウンドは以下のようにして取り行われます。

• それぞれの参加者は、自分の番号が割り当てられた対戦場が存在するならそこに行き、そこに来たもう一方の相手と対戦する。
• その後、それぞれの参加者が、自分の番号に $1$ を足す。もし $1$ を足した後の番号が $N+1$ であるなら、その値を $1$ に変更する。

$N$ 回のラウンドを通じて、二回以上同じ参加者と対戦するような参加者が存在しないようにしたいです。 このような条件を満たす対戦場への整数の割り当てをひとつ出力してください。 ただし、与えられる制約のもとでそのような割り当てが必ず存在することが示せます。

制約

• $1 \leq M$
• $M \times 2 +1 \leq N \leq 200000$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

出力

以下の形式で $M$ 行に出力せよ。 $i$ 行目には $i$ 個目の対戦場に割り当てる二つの整数を出力せよ。

$a_1$ $b_1$

$a_2$ $b_2$

$:$

$a_M$ $b_M$

4 1

2 3

参加者 $4$ 人を $A,B,C,D$ とし、はじめ A には $1$、Bには $2$、Cには $3$、Dには $4$ が割り振られているとします。

• $1$ 回目のラウンドでは $2$ の割り振られた B と $3$ の割り振られた C が対戦し、A の番号が $2$ 、B の番号が $3$、Cの番号が $4$、D の番号が $1$となります。
• $2$ 回目のラウンドでは $2$ の割り振られた A と $3$ の割り振られた B が対戦し、A の番号が $3$ 、B の番号が $4$、C の番号が $1$、D の番号が $2$ となります。
• $3$ 回目のラウンドでは $2$ の割り振られた D と $3$ の割り振られた A が対戦し、A の番号が $4$ 、B の番号が $1$、C の番号が $2$、D の番号が $3$ となります。
• $4$ 回目のラウンドでは $2$ の割り振られた C と $3$ の割り振られた D が対戦し、A の番号が $1$ 、B の番号が $2$、C の番号が $3$、D の番号が $4$ となります。

$4$ 回のラウンドを通じて二回以上同じ参加者と対戦するような参加者が存在しないため、この出力は正解となります。

7 3

1 6
2 5
3 4