Задача C. Очень скоростной трамвай
Задачу добавил: alef
Успешно сдано решений: 231
Организаторы чемпионата решили, что добираться до стадиона болельщики будут на трамвае. Для этого существующий трамвайный маршрут, состоящий из n остановок, продлили и дополнили ещё одной остановкой «Стадион».
Однако выяснилось, что поездка на трамвае занимает немало времени. Мэру города S пришла в голову отличная идея: сократить количество трамвайных остановок. Проведя некоторые подсчёты, он решил оставить ровно две остановки: новую — «Стадион» и одну из имеющихся n остановок.
По заданию мэра специалисты по транспорту провели исследование и выяснили, что в настоящее время трамвайным маршрутом пользуется m человек. Для каждого из этих m человек известно, на какой остановке sj он садится в трамвай и на какой остановке fj выходит из трамвая.
Когда из имеющихся n остановок останется одна, пассажиру, который пожелает воспользоваться трамваем, придётся пешком дойти от остановки, где он обычно садился в трамвай, до оставшейся остановки, доехать до остановки «Стадион», а затем дойти от остановки «Стадион» до остановки, где он обычно выходил.
Конечно, пассажир может переквалифицироваться в пешехода и просто дойти пешком от остановки, где он обычно садился, до остановки, где он обычно выходил, т.е. проделать путь длиной в fj - sj остановок.
Мэр полагает, что если путь длиной в fj - sj остановок окажется меньше, нежели пешеходная часть пути с использованием трамвая, пассажир совершенно точно пойдёт пешком.
Мэр ещё не решил, какую из имеющихся остановок он хочет оставить. У него есть список вариантов, и для каждого из них он хотел бы знать, какое количество пассажиров воспользуется трамваем. Ваша задача — определить это количество для каждого номера остановки из списка мэра.
В первой строке содержатся целые числа n, m, q (2 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105, 1 ≤ q ≤ 3·105) — количество остановок в маршруте, количество пассажиров, пользующихся маршрутом и количество запросов.
Во второй строке содержится m целых чисел s1, s2, ..., sm (1 ≤ sj ≤ n - 1, j = 1, 2, ..., m), где sj — номер остановки, на которой пассажир #j обычно садится в трамвай.
В третьей строке содержится m целых чисел f1, f2, ..., fm (2 ≤ fj ≤ n, j = 1, 2, ..., m), где fj — номер остановки, на которой пассажир #j обычно выходит из трамвая. Гарантируется, что sj < fj для всех j.
В четвёртой строке содержится q целых чисел r1, r2, ..., rq (1 ≤ rk ≤ n, k = 1, 2, ..., q), где rk — номер оставшейся остановки, для которой нужно вычислить количество пассажиров, воспользовавшихся трамваем.
Выведите q чисел p1, p2, ..., pk.
Число pk (1 ≤ k ≤ q) — это количество пассажиров, которые воспользуются трамваем, если единственной оставшейся из имеющихся остановок будет остановка #rk.
При выводе разделяйте числа пробелами или переводами строк.
Подзадача 1 (до 20 баллов)
2 ≤ n ≤ 100, 1 ≤ m, q ≤ 100
Баллы начисляются в случае прохождения всех тестов группы.
Подзадача 2 (до 80 баллов)
Все величины из условия могут принимать любые допустимые значения.
Баллы начисляются в случае прохождения всех тестов группы.
По запросу сообщается номер первого непройденного теста в группе.
5 14 4
2 1 3 3 4 2 1 2 2 1 3 3 4 2
4 3 4 5 5 3 3 5 4 3 5 4 5 4
2 4 3 2
6 5 3 6