Джинкс и лагерь миротворцев

Джинкс планирует планируют нападение на лагерь миротворцев.

База миротворцев представляется, как поле на координатной плоскости.

Героиня знает, что на страже лагеря $n$ миротворцев. Каждый из них имеет силу $v\_i$. Каждый страж отвечает за некоторый прямоугольник на координатной плоскости. Каждый прямоугольник задается координатами левой верхней и правой нижней точки, то есть парой точек $(x\_1, y\_1)$, $(x\_2, y\_2)$ ($x\_1 \leqslant x\_2$ и $y\_1 \leqslant y\_2$). Будем считать, что точка $(x, y)$ защищается стражем, отвечающим за прямоугольник $(x\_1, y\_1)$, $(x\_2, y\_2)$, если $x\_1 \leqslant x \leqslant x\_2$ и $y\_1 \leqslant y \leqslant y\_2$.

Одна точка базы может защищаться несколькими стражами, то есть прямоугольники за которые они отвечают могут пересекаться. К сожалению (или к счастью для Джинкс), от этого мало пользы, так как защищенность точки $(x, y)$ на базе $s\_{x, y}$ равна минимальной силе среди всех миротворцев.

К базе миротворцев существует $m$ подходов. $j$-й подход ведет или ко всем точкам внутри прямоугольника, заданного крайними точками $(x, y\_1)$ и $(x, y\_2)$, или прямоугольника, заданного крайними точками $(x\_1, y)$ и $(x\_2, y)$. То есть выбрав некоторый подход, может попасть в точку $(\overline{x}, \overline{y})$ базы миротворцев, если (в зависимости от вида подхода) $\overline{x} = x$ и $y\_1 \leqslant y \leqslant y\_2)$ или $\overline{y} = y$ и $x\_1 \leqslant x \leqslant x\_2)$.

Для каждого из подходов Джинкс хочет узнать минимальную защищенности среди всех точек, в которые она может попасть через этот подход и которые защищаются миротворцами, то есть найти $\min\limits\_{\overline{x}, \overline{y}} s \_{\overline{x},\overline{y}}$, для всех $(\overline{x},\overline{y})$, если (в зависимости от вида подхода) $\overline{x} = x$ и $y\_1 \leqslant y \leqslant y\_2$ или $\overline{y} = y$ и $x\_1 \leqslant x \leqslant x\_2$, в которых есть хотя бы один миротворец. Если ни в одна из точек выбранного подхода не защищается миротворцами, выведите $-1$.

В первой строке находятся два целых числа $n$ и $m$ ($1 \leqslant n \leqslant 3 \cdot 10^4$; $1 \leqslant m \leqslant 10^5$) --- количество стажей и количество подходов к базе.

В следующих $n$ строках следует описание охранников базы. Строка номер $i$ содержит пять целых чисел $x\_{i, 1}$, $x\_{i, 2}$, $y\_{i, 1}$, $y\_{i, 2}$ и $v\_i$ --- $x$-координата верхней левой точки, $x$-координата нижней правой точки, $y$-координата верхней левой точки, $y$-координата нижней правой точки $i$-го прямоугольника, за который отвечает $i$-й миротворец, а также его сила ($0 \leqslant x\_{i, 1}, x\_{i, 2}, y\_{i, 1}, y\_{i, 2} \leqslant 2 \cdot 10^5$; $0 \leqslant v\_i \leqslant 10^9$).

В следующих $m$ строках следует описание подходов.

Первый символ описания подхода равен либо 'x', либо 'y'. Если вида подхода равен 'x', то этот подход имеет вид $(x, y\_1)$ и $(x, y\_2)$, и далее через пробел даны координаты прямоугольника $x\_j$, $y\_{j, 1}$ и $y\_{j, 2}$. Иначе --- это подход типа $(x\_1, y)$ и $(x\_2, y)$, и далее идут координаты прямоугольника $y\_{j}$, $x\_{j, 1}$ и $x\_{j, 2}$.

Для каждого из $m$ подходов выведите минимальную защищенности среди всех точек, в которых есть миротворцы и в которые она может попасть через этот подход в отдельной строке. Если ни одна из точек, в которые ведет этот подход, не защищается хотя бы одним миротворцем, выведите $-1$.