Вам необходимо настроить очень сложную водораспределительную систему. Система состоит из \(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\) таким образом, чтобы все ограничения на входные и выходные потоки соблюдались?
Выходные данные
Если можно выбрать целые числа \(f_1, f_2, \dots, f_m\) таким образом, что все ограничения на входные и выходные потоки соблюдаются, то выведите «Possible» в первой строке. После выведите \(m\) строк, в \(i\)-й строке должно быть записано число \(f_i\) — выбранные настройки труб. Трубы пронумерованы в порядке, в котором появляются во входных данных.
В противном случае выведите «Impossible» в единственной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 -10 6 1
5
1 2
3 2
2 4
3 4
3 1
|
Possible
4
-6
8
-7
7
|
|
2
|
4
3 -10 6 4
5
1 2
3 2
2 4
3 4
3 1
|
Impossible
|