外部サイトへ移動します

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

別タブで開く

E - Forced Super Arcaea Online

作成者 sevenc_nanashi

テスター unbakedbread

配点 300 点

実行時間制限
2 秒
メモリ制限
512 MiB

問題文

ラグランジュさんは月額FFメモリーのSuper Arcaea Onlineに加入しようとしています。
月の二日目にFFメモリー以上を持っている場合、自動的にFFメモリーを消費してSuper Arcaea Onlineに加入、あるいは契約を継続します。
逆に、月の二日目にFFメモリー未満しか持っていない場合、Super Arcaea Onlineは自動的に解約されます。

ラグランジュさんは、AiA_iヶ月目の月の一日目にBiB_iメモリーを購入します。また、最初の購入を行うまではメモリーを持っていません。

QQ個の問題が与えられます。各XjX_jについて、以下の問題を解いてください:

ラグランジュさんがXjX_jヶ月目の月の三日目時点で、Super Arcaea Onlineに加入しているかどうかと、現在のメモリーがいくつかを求めてください。

ただし、ラグランジュさんはメモリーをSuper Arcaea Onlineの利用にしか使わないものとします。

制約

  • 入力される値はすべて整数
  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤F≤1091 \leq F \leq 10^9
  • 1≤Q≤1051 \leq Q \leq 10^5
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • Ai<Ai+1(1≤i≤N−1)A_i < A_{i+1} \quad (1 \leq i \leq N-1)
  • 1≤Bi≤1091 \leq B_i \leq 10^9
  • 1≤Xj≤1091 \leq X_j \leq 10^9
  • Xj<Xj+1(1≤j≤Q−1)X_j < X_{j+1} \quad (1 \leq j \leq Q-1)

入力

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

NFN \quad F A1B1A_1 \quad B_1 A2B2A_2 \quad B_2 ⋮\vdots ANBNA_N \quad B_N QQ X1X_1 X2X_2 ⋮\vdots XQX_Q

出力

QQ行出力してください。各行は、以下の形式で出力してください。

yjzjy_j \quad z_j

ここで、

  • yjy_jはラグランジュさんがXjX_jヶ月目の月の三日目時点でSuper Arcaea Onlineに加入している場合はYes、加入していない場合はNoです。
  • zjz_jはラグランジュさんがXjX_jヶ月目の月の三日目時点で持っているメモリーの量です。

サンプル 1

入力

3 100
2 250
5 50
7 180
8
1
2
3
4
5
6
7
8

出力

No 0
Yes 150
Yes 50
No 50
Yes 0
No 0
Yes 80
No 80

月額は100100メモリーです。 各月のメモリー量と加入状況は、以下のとおりです。

月 1 2 3 4 5 6 7 8
1日目(購入後)の残高 0 250 150 50 100 0 180 80
3日目の加入状況 No Yes Yes No Yes No Yes No
3日目の残高 0 150 50 50 0 0 80 80

現在のメモリーがFF未満の場合は、そのメモリーは使われずに繰り越されることに注意してください(4ヶ月目)。

サンプル 2

入力

3 10
1 3
2 4
3 5
4
1
2
3
4

出力

No 3
No 7
Yes 2
No 2

各回の購入量がFF未満でも、メモリーは繰り越されます。 33ヶ月目の購入後には3+4+5=123 + 4 + 5 = 12メモリーとなり、1010メモリーを消費して加入します。

サンプル 3

入力

3 1
1 1000000000
2 1000000000
3 1000000000
4
1
2
3
1000000000

出力

Yes 999999999
Yes 1999999998
Yes 2999999997
Yes 2000000000

残高が32bit符号付き整数に収まらない場合があります。 10910^9ヶ月目まで毎月加入し続け、合計10910^9メモリーを消費します。

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