В Академии Невермор по длинному коридору (его можно считать числовой прямой) стоят $n$ обитателей. У $i$-го обитателя есть:

\begin{itemize}
    \item координата на коридоре $x_i$;
    \item личный запас ума $m_i$;
    \item показатель командной работы $z_i$;
    \item особый трюк: он может временно уменьшить свой ум и повысить командную работу.
\end{itemize}

Формально, у $i$-го обитателя есть два числа $c_i$ и $a_i$. В любой момент (за нулевое время) он может заменить своё текущее значение ума на

$$\left\lfloor \frac{\text{текущий ум}}{c_i} \right\rfloor$$

и одновременно увеличить свою командную работу на $a_i$. Этой операцией можно пользоваться произвольное количество раз, если это выгодно.

Обитатели могут перемещаться по коридору: за единицу времени каждый обитатель может сместиться по прямой на $+1$ или $-1$.

Если несколько обитателей в некоторый момент времени оказались в одной и той же точке коридора, они могут объединиться в команду. Тогда:

\begin{itemize}
    \item ум команды равен сумме умов всех участвующих обитателей;
    \item командная работа команды равна минимуму по командной работе всех участвующих обитателей.
\end{itemize}

В академии возникают $q$ независимых инцидентов. Для каждого инцидента известны:
\begin{itemize}
    \item координата $y_j$~--- место, где нужно собрать команду;
    \item требуемый ум $s_j$;
    \item требуемая командная работа $t_j$.
\end{itemize}

Необходимо определить, за какое минимальное время в точке $y_j$ можно собрать такую команду из имеющихся обитателей (с учётом их перемещений и применения трюков), чтобы суммарный ум команды был не меньше $s_j$, а командная работа команды не меньше $t_j$. Если собрать такую команду невозможно, следует вывести $-1$.