Выполнить план, но не перевыполнить

Это интерактивная задача.

Требуется разработать планы производства автомобилей и запасных частей в некоторой стране.

Всего в стране $n$ городов, в которых расположены заводы, задействованные в производстве. В $i$-м городе на заводе могут работать от $l\_i$ до $r\_i$ человек включительно.

Некоторые города соединены двусторонними дорогами, при этом дорожная сеть имеет форму дерева: от каждого города можно единственным способом добраться до любого другого города, не проезжая через один город дважды.

Планом производства будем называть последовательность целых чисел $\[a\_1, a\_2, \ldots, a\_n]$, где $a\_i$ --- количество человек, которые будут работать на $i$-м заводе ($l\_i \leq a\_i \leq r\_i$). После формирования плана производства некоторые заводы будут выбраны как сборочные, они будут производить автомобили, а остальные будут производить запчасти. Выбор считается рациональным, если никакие два сборочных завода не соединены дорогой напрямую. Среди всех возможных рациональных выборов будет выбран тот, для которого суммарное количество работников сборочных заводов будет максимально. Это число называется эффективностью плана $\[a\_1, a\_2, \ldots, a\_n]$.

В этой задаче для некоторых значений $v\_1, v\_2, \ldots, v\_q$ вам необходимо выяснить, существует ли план с эффективностью $v\_i$. Если такой план существует, вам может потребоваться предъявить такой план.

Зафиксированы целочисленные параметры $x$, $y$ и $m$. Рассмотрим план $\[a\_1, a\_2, \ldots, a\_n]$. Сертификатом этого плана назовем число $k = \bigoplus\limits\_{j=1}^{n}\left((x\cdot j + y\cdot a\_j^2) \bmod m\right)$, где $\bigoplus$ --- это операция <<побитового исключающего или>>.

Напомним, что эта операция обозначается <<xor>> в Паскале и Python, <<\char 94>> в C++ и Java; для двух целых чисел она определена следующим образом: $i$-й бит результата равен $1$ тогда и только тогда, когда в одном из чисел этот бит $1$, а в другом $0$. Например, $6 \oplus 10 = 110\_2 \oplus 1010\_2 = 1100\_2 = 12$.

Процесс составления планов будет состоять из двух этапов.

На первом этапе вам будут даны значения $v\_1, v\_2, \ldots, v\_q$. Для каждого из них вам необходимо выяснить, существует ли план с эффективностью $v\_i$ и, если его не существует, вывести для этого запроса $-1$, а если существует, то неотрицательное целое число $k\_i$.

На втором этапе некоторые планы будут проверены: $c$ раз вам будет дано целое число $i$ ($1 \le i \le q$). В ответ на такой запрос требуется либо вывести $-1$, если плана с эффективностью $v\_i$ не существует, либо предоставить план $\[a\_1, a\_2, \ldots, a\_n]$, сертификат которого равен $k\_i$, а эффективность равна $v\_i$.

Предоставление сертификатов составленных планов и последующая проверка будут реализованы в интерактивном режиме. До того, как вы предоставите сертификаты, вы не будете знать, какие планы будут проверены. Поэтому в тех подзадачах, в которых $c > 0$, необходимо еще на первом этапе подготовиться к проверке, выведя для значений эффективности $v\_i$, где искомый план существует, такие значения $k\_i$, для которых вы сможете на втором этапе предъявить план с сертификатом, равным $k\_i$.