外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

T - Massive Excessive Impressive Cat Food

作成者 nekooooooo、siooisi、jammy、trueryob

テスター siooisi、tau0529、trueryob

配点 525 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

わりとねこくんの餌箱には、最初キャットフードが 00 個入っています。

整数 KK と MM 組の整数 (aj,bj)(a_j,b_j) が与えられます。わりとねこくんがびっくりして逃げ出す閾値 UU を、次のように定めます。

U=∑j=1MajKbjU = \sum_{j=1}^{M} a_j K^{b_j}

餌箱に対する QQ 個のクエリを、与えられた順に処理します。ii 番目のクエリでは、整数 ti,xi,yit_i,x_i,y_i が与えられます。

  • ti=1t_i=1 のとき、餌箱にキャットフードを xiKyix_i K^{y_i} 個追加します。
  • ti=2t_i=2 のとき、餌箱のキャットフードの個数から xiKyix_i K^{y_i} を引きます。引いた結果は負になることもあります。

各クエリの直後のキャットフードの個数を CC とします。

  • C≥UC \ge U なら、わりとねこくんはびっくりして逃げ出します。その時点で処理を打ち切り、結果を byebye, neko! とします。
  • C<0C < 0 なら、世界の理が崩れます。その時点で処理を打ち切り、結果を byebye, world! とします。
  • 0≤C<U0 \le C < U なら、次のクエリに進みます。

すべてのクエリの直後に 0≤C<U0 \le C < U を満たした場合、結果を yum とします。

制約

  • 2≤K≤10142 \le K \le 10^{14}
  • 1≤M,Q≤40001 \le M,Q \le 4000
  • 1≤aj≤K−11 \le a_j \le K-1 (1≤j≤M)(1 \le j \le M)
  • 0≤bj≤10140 \le b_j \le 10^{14} (1≤j≤M)(1 \le j \le M)
  • ti∈{1,2}t_i \in \{1,2\} (1≤i≤Q)(1 \le i \le Q)
  • 1≤xi≤K−11 \le x_i \le K-1 (1≤i≤Q)(1 \le i \le Q)
  • 0≤yi≤10140 \le y_i \le 10^{14} (1≤i≤Q)(1 \le i \le Q)
  • 入力はすべて整数

入力

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

KMQK \quad M \quad Q a1b1a_1 \quad b_1 a2b2a_2 \quad b_2 ⋮\vdots aMbMa_M \quad b_M t1x1y1t_1 \quad x_1 \quad y_1 t2x2y2t_2 \quad x_2 \quad y_2 ⋮\vdots tQxQyQt_Q \quad x_Q \quad y_Q

出力

結果を byebye, neko!、byebye, world!、yum のいずれかで 11 行に出力してください。

入力例 1

10 1 3
1 2
1 9 1
1 9 0
1 1 0

出力例 1

byebye, neko!

閾値は U=1⋅102=100U=1\cdot 10^2=100 です。各クエリの直後のキャットフードの個数は次のようになります。

  • 11 番目のクエリでは 9⋅101=909\cdot 10^1=90 個を追加し、0+90=900+90=90 個になります。
  • 22 番目のクエリでは 9⋅100=99\cdot 10^0=9 個を追加し、90+9=9990+9=99 個になります。
  • 33 番目のクエリでは 1⋅100=11\cdot 10^0=1 個を追加し、99+1=10099+1=100 個になります。

33 番目のクエリの直後に個数が閾値 UU に達するため、byebye, neko! を出力します。

入力例 2

2 1 3
1 5
1 1 3
2 1 0
2 1 3

出力例 2

byebye, world!

閾値は U=1⋅25=32U=1\cdot 2^5=32 です。

  • 11 番目のクエリでは 1⋅23=81\cdot 2^3=8 個を追加し、0+8=80+8=8 個になります。
  • 22 番目のクエリでは 1⋅20=11\cdot 2^0=1 個を引き、8−1=78-1=7 個になります。
  • 33 番目のクエリでは 1⋅23=81\cdot 2^3=8 個を引き、7−8=−17-8=-1 個になります。

33 番目のクエリの直後に個数が負になるため、byebye, world! を出力します。

入力例 3

3 1 2
1 100000000000000
1 2 99999999999999
2 1 0

出力例 3

yum

閾値は U=31014U=3^{10^{14}} です。

  • 11 番目のクエリでは 2⋅31014−12\cdot 3^{10^{14}-1} 個を追加し、2⋅31014−12\cdot 3^{10^{14}-1} 個になります。
  • 22 番目のクエリでは 1⋅30=11\cdot 3^0=1 個を引き、2⋅31014−1−12\cdot 3^{10^{14}-1}-1 個になります。

どちらのクエリの直後も個数は 00 以上 UU 未満なので、yum を出力します。

入力例 4

2 2 3
1 100000000000000
1 0
1 1 100000000000000
2 1 100000000000000
2 1 0

出力例 4

byebye, world!

参加受付は終了しました。