eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Темные ночи

Темные ночи

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Маленький Петя очень любит свою работу. Он работает охранником в ночную смену и есть N башен, которые он должен защитить. Каждая башня содержит лампочку, которая может гореть, либо быть сломанной. Помимо этого, внутри каждой башни хранится некоторое количество сокровищ. Петя знает, что каждую ночь воры могут попытаться украсть сокровища. Однако, они боятся темноты, поэтому они могут попытаться украсть что-либо только из башен, которые содержат работающую лампочку. Каждую ночь некоторые лампочки чинят, а некоторые ломаются. Более точно, согласно Неизвестному Вселенскому Закону, состояние лампочки P[i] будем таким же, как и состояние лампочки i предыдущей ночью. Помимо этого, все P[i] различны.

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

Входные данные

Первая строка входных данных содержит количество башен N (1N10^5). Следующая строка содержит N различных целых чисел от 1 до N. i-ое число во второй строчке — это P[i]. Третья строка содержит N целых чисел от нуля до 10^6. i-ое число в третьей строке равняется количеству сокровищ в i-ой башне. Четвертая строка содержит строку из N символов. Каждый из символов — это либо 0, либо 1. i-ый символ равен 0 если лампочка в i-ой башне поломана и равен 1 в противном случае. Пятая строка содержит целое число M (1M10^5) — количество ночей, которые хочет проверить Петя.

Выходные данные

Выходные данные должны содержать ровно M строк. i-ая строка выходных данных должна равняться количеству сокровищ по модулю 10^9+7, которые могут быть гипотетически украдены в течение i-ой ночи.

Пример

Входные данные #1
2
2 1
3 4
10
10
Выходные данные #1
3
4
3
4
3
4
3
4
3
4
Автор Евгений Соболев
Источник III Международная Летняя школа программирования 2013 г. Севастополь