F. Управление потоками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам необходимо настроить очень сложную водораспределительную систему. Система состоит из $$$n$$$ узлов и $$$m$$$ труб, $$$i$$$-я труба соединяет узлы $$$x_i$$$ и $$$y_i$$$.

Вам нужно всего лишь подобрать настройки труб. Требуется выбрать $$$m$$$ целых чисел $$$f_1$$$, $$$f_2$$$, ..., $$$f_m$$$ для того, что использовать их в качестве настроек соответствующих труб. $$$i$$$-я труба будет пересылать $$$f_i$$$ единиц воды в секунду из узла $$$x_i$$$ в узел $$$y_i$$$ (если $$$f_i$$$ отрицательно, то труба будет пересылать $$$|f_i|$$$ единиц воды из узла $$$y_i$$$ в узел $$$x_i$$$). Разрешается выставлять $$$f_i$$$ значение от $$$-2 \cdot 10^9$$$ до $$$2 \cdot 10^9$$$.

Для корректной работы системы необходимо также соблюдать следующие ограничения: для каждого $$$i \in [1, n]$$$, $$$i$$$-му узлу присвоено число $$$s_i$$$, означающее, что разница между входным и выходным потоками для $$$i$$$-го узла должна быть ровно $$$s_i$$$ (если $$$s_i$$$ неотрицательно, то $$$i$$$-й узел должен принимать $$$s_i$$$ единиц воды; если отрицательно, то $$$i$$$-й узел должен отдавать $$$|s_i|$$$ единиц воды другим узлам).

Можно ли выбрать целые числа $$$f_1$$$, $$$f_2$$$, ..., $$$f_m$$$ таким образом, чтобы все ограничения на входные и выходные потоки соблюдались?

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

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество узлов.

Во второй строке записаны $$$n$$$ целых чисел $$$s_1, s_2, \dots, s_n$$$ ($$$-10^4 \le s_i \le 10^4$$$) — ограничения для узлов.

В третьей строке записано одно целое число $$$m$$$ ($$$0 \le m \le 2 \cdot 10^5$$$) — количество труб.

В $$$i$$$-й из следующих $$$m$$$ строк записаны два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) — описание $$$i$$$-й трубы. Гарантируется, что каждая неупорядоченная пара $$$(x, y)$$$ встретится во входных данных не более одного раза (это значит, что после первого вхождения $$$(x, y)$$$ не будет пар $$$(x, y)$$$ и $$$(y, x)$$$). Гарантируется, что для каждой пары узлов существует некоторый путь по трубам, соединяющий их.

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

Если можно выбрать целые числа $$$f_1, f_2, \dots, f_m$$$ таким образом, что все ограничения на входные и выходные потоки соблюдаются, то выведите «Possible» в первой строке. После выведите $$$m$$$ строк, в $$$i$$$-й строке должно быть записано число $$$f_i$$$ — выбранные настройки труб. Трубы пронумерованы в порядке, в котором появляются во входных данных.

В противном случае выведите «Impossible» в единственной строке.

Примеры
Входные данные
4
3 -10 6 1
5
1 2
3 2
2 4
3 4
3 1
Выходные данные
Possible
4
-6
8
-7
7
Входные данные
4
3 -10 6 4
5
1 2
3 2
2 4
3 4
3 1
Выходные данные
Impossible