AT_abc417_d [ABC417D] Takahashi's Expectation

高橋くんは、これから $ N $ 個のプレゼントをもらいます。 高橋くんにはテンションという非負整数のパラメータがあり、テンションはプレゼントをもらうごとに変動します。 それぞれのプレゼントは価値 $ P $ 、テンション上げ度 $ A $ 、テンション下げ度 $ B $ という $ 3 $ つのパラメータをもち、これらのパラメータによって高橋くんのテンションは次のように変動します。 - もらったプレゼントの価値 $ P $ がテンションの値以上であるとき、高橋くんはプレゼントに喜び、テンションが $ A $ だけ増加する。 - もらったプレゼントの価値 $ P $ がテンションの値より小さいとき、高橋くんはプレゼントにがっかりし、テンションが $ B $ だけ減少する。ただし、高橋くんのテンションの値が $ B $ より小さかった場合、高橋くんのテンションは $ 0 $ になる。 $ i $ 番目 $ (1\le i\le N) $ に受け取るプレゼントの価値は $ P _ i $ 、テンション上げ度は $ A _ i $ 、テンション下げ度は $ B _ i $ です。 $ Q $ 個の質問が与えられるので、その全てに答えてください。 $ i $ 番目 $ (1\le i\le Q) $ の質問では、非負整数 $ X _ i $ が与えられるので次の質問に答えてください。 > 高橋くんのテンションがはじめ $ X _ i $ だったときの、 $ N $ 個のプレゼントをすべて受け取ったあとの高橋くんのテンションを求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P _ 1 $ $ A _ 1 $ $ B _ 1 $ $ P _ 2 $ $ A _ 2 $ $ B _ 2 $ $ \vdots $ $ P _ N $ $ A _ N $ $ B _ N $ $ Q $ $ X _ 1 $ $ X _ 2 $ $ \vdots $ $ X _ Q $

$ Q $ 行にわたって出力せよ。 $ i $ 行目には、 $ i $ 番目の質問に対する答えを出力せよ。

### Sample Explanation 1 高橋くんのテンションがはじめ $ 10 $ だったとき、高橋くんのテンションは以下のように変動します。 - $ 1 $ つめのプレゼントの価値 $ 3 $ は高橋くんのテンション $ 10 $ 未満なので、テンション下げ度 $ 4 $ だけ高橋くんのテンションが減少し、高橋くんのテンションが $ 6 $ になる。 - $ 2 $ つめのプレゼントの価値 $ 1 $ は高橋くんのテンション $ 6 $ 未満で、高橋くんのテンション $ 6 $ はテンション下げ度 $ 9 $ 未満なので、高橋くんのテンションが $ 0 $ になる。 - $ 3 $ つめのプレゼントの価値 $ 2 $ は高橋くんのテンション $ 0 $ 以上なので、テンション上げ度 $ 6 $ だけ高橋くんのテンションが増加し、高橋くんのテンションが $ 6 $ になる。 - $ 4 $ つめのプレゼントの価値 $ 3 $ は高橋くんのテンション $ 6 $ 未満で、高橋くんのテンション $ 6 $ はテンション下げ度 $ 8 $ 未満なので、高橋くんのテンションが $ 0 $ になる。 よって、最終的な高橋くんのテンションは $ 0 $ になります。 ### Sample Explanation 2 高橋くんのテンションが高すぎるため、最高のプレゼントを貰っていても高橋くんのテンションは下がり続けます。 ### Constraints - $ 1\le N\le10000 $ - $ 1\le P _ i\le500\ (1\le i\le N) $ - $ 1\le A _ i\le500\ (1\le i\le N) $ - $ 1\le B _ i\le500\ (1\le i\le N) $ - $ 1\le Q\le5\times10 ^ 5 $ - $ 0\le X _ i\le10 ^ 9\ (1\le i\le Q) $ - 入力はすべて整数