2143. Войны планет

Все большую и большую популярность набирает игра "Войны планет". Правила игры предельно просты. На плоскости расположены `n` планет, каждая из которых характеризуется координатами своего место положения `x_i`, `y_i` и скоростью производства космических кораблей `s_i`. В игру играют два игрока. Изначально каждый игрок имеет в своем распоряжении одну планету, а все остальные планеты в начале игры являются нейтральными. Также на каждой планете в начале находится некоторое число кораблей `p_i`. На нейтральных планетах – это нейтральные войска, а на планетах игроков – это войска соответствующих игроков.

Игра состоит из раундов. В начале каждого раунда на планетах, не являющихся нейтральными, появляются дополнительные `s_i` кораблей. Корабли мгновенно оказываются в распоряжении игрока, владеющего соответствующей планетой.

После этого игроки начинают пересылать войска с планеты на планету, при этом игрок может посылать корабли только с планет, которые ему принадлежат, и только не больше кораблей, чем на этой планете есть. Если игрок пересылает корабли с планеты с координатами `("sx",\ "sy")` на планету с координатами `("dx",\ "dy")`, то корабли прибывают к планете назначения после `|~\ sqrt{("sx"\ -\ "dx")^2\ +\ ("sy"-"dy")^2}\ ~|` раундов (`|~a~|` означает минимальное целое число, не меньшее `a`).

Затем происходит прибытие войск на планеты.

В конце раунда, если на какой-то планете оказываются войска обоих игроков, то они вступают в бой. В результате сражения у каждого из игроков уничтожается `x\ =\ min(p_1,p_2)` кораблей, где `p_1` – число кораблей первого игрока на этой планете, а `p_2` – второго. После этого, если на планете остались войска игрока и нейтральные войска, то в бой вступают они, при этом бой происходит по тем же правилам.

После всех сражений, если на планете более нуля кораблей какого-то игрока, то он захватывает планету. Иначе владелец планеты остается неизменным. На этом раунд заканчивается.

Напишите программу, которая обрабатывала бы события игры, а также могла отвечать на запросы про `i`-ую планету, сколько на ней войск и кто ею владеет.

В первой строке входного файла целое число `n` (`2\ ≤\ n\ ≤\ 100`) – число планет. Далее следуют `n` строк, по четыре целых числа `x`, `y`, `s` и `p` в каждой. Числа `x` и `y` (`|x|,\ |y|\ ≤\ 20`) – координаты соответствующей планеты, `s` (`0\ ≤\ s\ ≤\ 10`) – скорость производства кораблей, `p` (`0\ ≤\ p\ ≤\ 100`) – количество кораблей на планете в начале игры. В следующей строке следуют два целых числа  – номера планет первого и второго игроков. Планеты нумеруются с единицы в порядке появления во входном файле. Гарантируется, что координаты всех планет различны.

В следующей строке входного файла одно целое число `m` (`0\ ≤\ m\ ≤\ 1000`) – количество событий и запросов, которые необходимо обработать. Каждый запрос занимает отдельную строку и начитается и с целого числа `t`, характеризующего тип события/запроса.

Если `t\ =\ 0`, то это означает конец раунда. Считается что все сражения происходят именно в момент конца раунда.

Если `t\ =\ 1`, то происходит пересылка войск. Тогда в строке далее идут три целых положительных числа `"sp"`, `"dp"` и `"ships"` – номер планеты, с которой отправляются корабли, номер планеты, на которую отправляются корабли, и число отправляемых кораблей соответственно. Гарантируется, что на планете `"sp"` будет не менее чем `"ships"` кораблей, планета `"sp"` не будет нейтральной и планеты `"sp"` и `"dp"` не совпадают.

Если `t\ =\ 2`, то далее идет целое число `"planet"` – номер планеты, о которой запрашивается информация.

Для каждого запроса о планете выведите в отдельной строке ее владельца и количество войск на ней на момент запроса. Следуйте формату примера. Считается что все запросы происходят после производства кораблей и до прибытия войск на планеты.

3
0 0 1 100
1 0 10 10
2 0 0 100
1 3
26
1 1 2 60
1 3 2 50
2 1
2 2
2 3
0
2 1
2 2
2 3
0
2 1
2 2
2 3
1 1 2 1
2 1
2 2
2 3
0
0
2 1
2 2
2 3
1 3 2 31
0
0
2 2

Player1 41
Neutral 10
Player2 50
Player1 42
Neutral 10
Player2 50
Player1 43
Neutral 0
Player2 50
Player1 42
Neutral 0
Player2 50
Player1 44
Player1 11
Player2 50
Player2 20

В примере войска, вылетающие в первом раунде, долетают до планеты `2` только во конце второго раунда. При этом в конце второго дня на планете `2` окажутся `10` нейтральных кораблей, `60` кораблей первого игрока и `50` – второго. После битвы кораблей игроков останутся `10` нейтральных кораблей и `10` кораблей первого игрока. После из сражения на планете `2` не будет ни одного корабля и она останется нейтральной.

В третьем раунде первый игрок высылает один корабль на планету `2`, который в конце четвертого раунда ее захватывает.

В пятом раунде второй игрок посылает `31` корабль на вторую планету, но когда они прибывают на планету `2` на ней уже есть `31` корабль первого игрока. Корабли полностью уничтожают друг друга, но планета остается под контролем первого игрока.