Темні ночі#5946

Темні ночі

2 секунди

64 мегабайти

Легка

Маленький Петя дуже любить свою роботу. Він працює охоронцем у нічну зміну і має $N$ веж, які він повинен захистити. Кожна вежа містить лампочку, яка може або світити, або бути зламаною. Окрім цього, всередині кожної вежі зберігається певна кількість скарбів. Петя знає, що кожної ночі злодії можуть спробувати викрасти скарби. Проте, вони бояться темряви, і тому можуть викрасти щось лише з веж із працюючою лампочкою.

Кожної ночі деякі лампочки ремонтують, а деякі ламаються. Точніше, згідно з Невідомим Всесвітнім Законом, стан лампочки у вежі $P_{i}$ P_i цієї ночі стає таким же, як і стан лампочки у вежі $i$ попередньої ночі. Крім того, всі $P_{i}$ P_i різні.

Тепер Петя хоче знати, яку максимальну кількість скарбів можуть викрасти злодії в першу ніч, другу, ..., $M$ -ту ніч. Всі злодії є цілком гіпотетичними, тому ми вважаємо, що на початку кожної ночі нічого не вкрадено. Протягом однієї ночі злодії можуть викрасти з будь-якої вежі з працюючою лампочкою, а також можуть викрасти з кількох веж за одну ніч.

Вхідні дані

Перший рядок містить одне ціле число $N$ ( $1 \leq N \leq 1 0^{5}$ 1 \leq N \leq 10^5) — кількість веж. Другий рядок містить $N$ різних цілих чисел від $1$ до $N$ : $P_{1}, P_{2}, \dots, P_{N}$ P_1, P_2, \ldots, P_N. Третій рядок містить $N$ цілих чисел $a_{1}, a_{2}, \dots, a_{N}$ a_1, a_2, \ldots, a_N ( $0 \leq a_{i} \leq 1 0^{6}$ 0 \leq a_i \leq 10^6), де $a_{i}$ a_i — кількість скарбів у $i$ -й вежі. Четвертий рядок містить рядок з $N$ символів — $0$ або $1$ . $i$ -й символ дорівнює $0$ , якщо лампочка у $i$ -й вежі не працює, і $1$ , якщо працює. П’ятий рядок містить одне ціле число $M$ ( $1 \leq M \leq 1 0^{5}$ 1 \leq M \leq 10^5) — кількість ночей, які хоче перевірити Петя.

Вихідні дані

Виведіть рівно $M$ рядків. $i$ -й рядок повинен містити кількість скарбів, які могли б бути гіпотетично викрадені протягом $i$ -ї ночі, за модулем $1 0^{9} + 7$ 10^9+7.

Приклади

Приклад 1