AT_abc319_e [ABC319E] Bus Stops

[problemUrl]: https://atcoder.jp/contests/abc319/tasks/abc319_e 高橋君ははじめ高橋君の家におり、これから青木君の家に遊びに行きます。 $ 2 $ 人の家の間には $ 1 $ から $ N $ までの番号がつけられた $ N $ 個のバス停があり、高橋君はそれらの間を下記の方法で移動できます。 - 高橋君の家からバス停 $ 1 $ まで $ X $ だけの時間をかけて徒歩で移動できます。 - 各 $ i\ =\ 1,\ 2,\ \ldots,\ N-1 $ について、バス停 $ i $ からは $ P_i $ の倍数である時刻それぞれにバスが出発し、そのバスに乗ることで $ T_i $ だけの時間をかけてバス停 $ (i+1) $ に移動できます。**ここで、$ 1\ \leq\ P_i\ \leq\ 8 $ が制約として保証されます。** - バス停 $ N $ から青木君の家まで、$ Y $ だけの時間をかけて徒歩で移動できます。 各 $ i\ =\ 1,\ 2,\ \ldots,\ Q $ に対して下記のクエリを処理してください。 > 高橋君が高橋君の家を時刻 $ q_i $ に出発するときの、高橋君が青木君の家に到着する時刻としてあり得る最も早いものを求めよ。 なお、バスの出発時刻ちょうどにそのバスが出発するバス停に到着した場合であっても、そのバスに乗ることができます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X $ $ Y $ $ P_1 $ $ T_1 $ $ P_2 $ $ T_2 $ $ \vdots $ $ P_{N-1} $ $ T_{N-1} $ $ Q $ $ q_1 $ $ q_2 $ $ \vdots $ $ q_Q $

$ Q $ 行出力せよ。 $ i\ =\ 1,\ 2,\ \ldots,\ Q $ について、$ i $ 行目には $ i $ 番目のクエリに対する答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ X,\ Y\ \leq\ 10^9 $ - $ 1\ \leq\ P_i\ \leq\ 8 $ - $ 1\ \leq\ T_i\ \leq\ 10^9 $ - $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ q_i\ \leq\ 10^9 $ - 入力はすべて整数 ### Sample Explanation 1 $ 1 $ 番目のクエリについて、高橋君は下記の通りに移動を行って、時刻 $ 34 $ に青木君の家に到着することができます。 - 時刻 $ 13 $ に高橋君の家を出発する。 - 高橋君の家から徒歩で移動し、時刻 $ 15 $ にバス停 $ 1 $ に到着する。 - 時刻 $ 15 $ にバス停 $ 1 $ を出発するバスに乗り、時刻 $ 19 $ にバス停 $ 2 $ に到着する。 - 時刻 $ 24 $ にバス停 $ 2 $ を出発するバスに乗り、時刻 $ 30 $ にバス停 $ 3 $ に到着する。 - 時刻 $ 30 $ にバス停 $ 3 $ を出発するバスに乗り、時刻 $ 31 $ にバス停 $ 4 $ に到着する。 - バス停 $ 4 $ から徒歩で移動し、時刻 $ 34 $ に青木君の家に到着する。 $ 2 $ 番目のクエリについて、高橋君は下記の通りに移動を行って、時刻 $ 22 $ に青木君の家に到着することができます。 - 時刻 $ 0 $ に高橋君の家を出発する。 - 高橋君の家から徒歩で移動し、時刻 $ 2 $ にバス停 $ 1 $ に到着する。 - 時刻 $ 5 $ にバス停 $ 1 $ を出発するバスに乗り、時刻 $ 9 $ にバス停 $ 2 $ に到着する。 - 時刻 $ 12 $ にバス停 $ 2 $ を出発するバスに乗り、時刻 $ 18 $ にバス停 $ 3 $ に到着する。 - 時刻 $ 18 $ にバス停 $ 3 $ を出発するバスに乗り、時刻 $ 19 $ にバス停 $ 4 $ に到着する。 - バス停 $ 4 $ から徒歩で移動し、時刻 $ 22 $ に青木君の家に到着する。