Монокарп играет в компьютерную игру «Гоблины и гномы». В этой игре он управляет подземным городом гномов, защищающимся от орд гоблинов.
Подземный город состоит из \(n\) залов и \(m\) односторонних туннелей, соединяющих некоторые пары залов. Структура туннелей такова, что, выйдя из какого-то зала, нельзя вернуться в него обратно по тоннелям.
На город готовится \(k\) атак гоблинов, в \(i\)-й атаке город атакуют \(i\) гоблинов. Цель Монокарпа — выдержать все \(k\) атак.
\(i\)-я атака происходит следующим образом: сначала \(i\) гоблинов появляются в каких-то залах города и грабят их, при этом в каждом зале появляется не более одного гоблина. После этого гоблины начинают перемещаться из зала в зал по туннелям, попутно грабя каждый зал на своем пути.
Гоблины очень жадные и хитрые, а поэтому планируют выбирать свои стартовые залы и пути так, что никакие два гоблина не пройдут через один и тот же зал. При этом, среди всех возможных планов атаки они выбирают такой, что позволяет в сумме разграбить максимальное количество залов. После того как гоблины разграбили максимальное количество залов, они покидают город.
Если в результате атаки все залы оказались разграблены — Монокарп проигрывает. Иначе гномам удается восстановить город. Если какой-то зал оказался разграблен в ходе атаки, то в ходе следующих атак он все равно представляет интерес для гоблинов (гномы успевают восстановить его).
Перед каждой атакой у Монокарпа есть время для подготовки. Монокарп может готовиться бесконечно долго (он сам решает, когда вызвать каждую атаку), но чем дольше он готовится к атаке, тем меньше очков он получает. Если Монокарп готовился к \(i\)-й атаке \(t_i\) минут, то после нее он получает \(\max(0, x_i - t_i \cdot y_i)\) очков (естественно, если он не проигрывает).
Во время подготовки к атаке Монокарп может блокировать туннели. За одну минуту он может заблокировать либо все туннели, ведущие в некоторый зал, либо все туннели, ведущие из некоторого зала. Если Монокарп заблокировал какой-то туннель во время подготовки к атаке, то этот туннель остается заблокированным и во время следующих атак.
Помогите Монокарпу выдержать все \(k\) атак гоблинов и набрать максимальное количество очков!
Выходные данные
Выведите оптимальную последовательность действий Монокарпа в следующем формате:
В первой строке выведите целое число \(a\) (\(k \le a \le 2n + k\)) — количество действий, которые совершает Монокарп. Во второй строке выведите сами эти действия в том порядке, в котором Монокарп их выполняет. \(i\)-е действие описывается целым числом \(b_i\) (\(-n \le b_i \le n\)) в следующем формате:
- если \(b_i > 0\), то Монокарп блокирует все туннели, ведущие из зала \(b_i\);
- если \(b_i < 0\), то Монокарп блокирует все туннели, ведущие в зал \(|b_i|\);
- если \(b_i = 0\), то Монокарп вызывает очередную атаку гоблинов.
Нельзя повторять одно и то же действие по блокировке \(b_i\) несколько раз. Каждый раз, когда Монокарп вызывает очередную атаку гоблинов, он должен выдержать ее (у гоблинов не должно быть возможности разграбить все залы города). Монокарп должен выдержать ровно \(k\) атак и получить максимально возможное количество очков.
Если существует несколько оптимальных последовательностей действий — выведите любую из них.
Примечание
В первом примере Монокарп сначала блокирует все туннели, ведущие в зал \(2\), а потом — все туннели, ведущие в зал \(3\), после чего вызывает все атаки. Он готовился к атаке \(1\) две минуты, поэтому он получает за нее \(98\) очков. К остальным атакам он не готовился, поэтому получает максимально возможные очки за них (\(200\), \(10\) и \(100\)). Суммарно он набирает \(408\) очков.
Во втором примере Монокарп сразу вызывает первую атаку и получает за нее \(100\) очков. Перед второй атакой он блокирует все туннели, ведущие в зал \(3\). Это означает, что он готовится к ней одну минуту и получает \(195\) очков за нее. К третьей атаке Монокарп не готовится и получает \(10\) очков. Перед четвертой атакой он блокирует туннели, ведущие из зала \(1\), это означает, что он готовится к атаке одну минуту и получает за нее \(99\) очков. Суммарно он набирает \(404\) очка.
В третьем примере Монокарпу не важно, сделает он одно действие или несколько перед единственной атакой, так как он в любом случае не получит за нее очков. А потому блокирует все туннели в городе, потратив на это целых \(5\) минут и переживает атаку, не получив за нее очков.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4 4
1 2
2 3
4 3
5 3
100 1
200 5
10 10
100 1
|
6
-2 -3 0 0 0 0
|
|
2
|
5 4 4
1 2
2 3
4 3
5 3
100 100
200 5
10 10
100 1
|
6
0 -3 0 0 1 0
|
|
3
|
5 10 1
1 2
1 3
1 4
1 5
5 2
5 3
5 4
4 2
4 3
2 3
100 100
|
6
1 2 3 4 5 0
|