Maximum 君と Merin ちゃんは経験値を獲得するべく、埼玉大学に生息するスライムを $Q$ 回に分けて討伐することにしました。
$i$ 回目の討伐では、$N_i$ 種類のスライムを討伐対象とし、 $j$ 種類目のスライムは体力が $H_{i,j}$ で $C_{i,j}$ 体存在します。

二人は以下の行動のうち 1 つを選んで行うことを交互に繰り返します。先手は Maximum 君です。

• スライムを 1 体選んで攻撃することで、スライムの体力を $d$ 減らす。ただし、二人が 1 回の攻撃で減らすことができる体力は最大で $D$ であり、 $d$ は $1 \leq d \leq D$ を満たす任意の整数である。
• スライムを 1 体選んで 2 体のスライムに分裂させる。ただし、分裂後のスライムの体力はともに正の整数であり、それらの和は元のスライムの体力に等しいものとする。

体力が 0 以下になったスライムは、その時点で倒されて消滅します。
討伐対象である最後の一体のスライムを倒した者だけが経験値を獲得できます。

各討伐において、両者が最適に行動した場合、経験値を取得できるのが Maximum 君であれば Maximum、Merin ちゃんであれば Merin と出力してください。

• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq D \leq 10^9$
• $1 \leq N_i \leq 2 \times 10^5$
• $1 \leq H_{i, j}, \ C_{i, j} \leq 10^9$
• $1 \leq \sum_{i=1}^{Q} N_i \leq 2 \times 10^5$
• 入力は全て整数である。

部分点

この問題はいくつかの小課題に分けられ、その小課題の全てのテストケースに正解した場合に、「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。

1. （20 点） $\sum_{i=1}^{Q} \sum_{j=1}^{N_i} H_{i,j} C_{i,j} \leq 30$ を満たす。
2. （30 点） $1 \leq H_{i, j} \leq 1000$ を満たす。
3. （50 点） 追加の制約はない。

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

$Q \ D$
$Query_1$
$Query_2$
$:$
$Query_Q$

ただし、 $Query_i$ は $i$ 個目の討伐であり、以下のいずれかの形式で与えられる。

$N$
$H_1 \ C_1$
$H_2 \ C_2$
$\vdots$
$H_N \ C_N$

Maximum 君が経験値を取得できるならば Maximum、Merin ちゃんが経験値を取得できるならば Merin を出力せよ。