28602번 - Джинкс и лагерь миротворцев 다국어

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

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

Героиня знает, что на страже лагеря $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$.