Jinx and the Peacekeeper Camp

Jinx plans an attack on a peacekeeper camp.

The camp is a field on the coordinate plane.

The camp has $n$ peacekeeper guards. Guard $i$ has strength $v_i$ and is responsible for one rectangle on the plane. Each rectangle is given by its upper left corner $(x_1, y_1)$ and lower right corner $(x_2, y_2)$, with $x_1 \leq x_2$ and $y_1 \leq y_2$. A point $(x, y)$ is protected by the guard of this rectangle if $x_1 \leq x \leq x_2$ and $y_1 \leq y \leq y_2$.

A point of the camp can be protected by several guards, and their rectangles may overlap. Unfortunately for Jinx, this helps little. The protection $s_{x,y}$ of point $(x, y)$ equals the smallest strength among the guards protecting it.

The camp has $m$ approaches. The $j$-th approach leads to all points inside one of two rectangles: either the rectangle with corners $(x, y_1)$ and $(x, y_2)$, or the rectangle with corners $(x_1, y)$ and $(x_2, y)$. Through a vertical approach, Jinx can reach a point $(\overline{x}, \overline{y})$ if $\overline{x} = x$ and $y_1 \leq \overline{y} \leq y_2$. Through a horizontal approach, she can reach it if $\overline{y} = y$ and $x_1 \leq \overline{x} \leq x_2$.

For each approach, find the minimum protection $s_{\overline{x},\overline{y}}$ over all points she can reach through it that are protected by at least one guard.

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 3 \cdot 10^4$, $1 \leq m \leq 10^5$), the number of guards and the number of approaches.

Each of the next $n$ lines describes one guard. Line $i$ contains five integers $x_{i,1}$, $x_{i,2}$, $y_{i,1}$, $y_{i,2}$ and $v_i$. The first four values are the coordinates of the upper left and lower right corners of the rectangle of guard $i$, and $v_i$ is the strength of that guard ($0 \leq x_{i,1}, x_{i,2}, y_{i,1}, y_{i,2} \leq 2 \cdot 10^5$, $0 \leq v_i \leq 10^9$).

Each of the next $m$ lines describes one approach. The first character of the line is either x or y. If it is x, the approach is defined by $(x, y_1)$ and $(x, y_2)$, and the line continues with $x_j$, $y_{j,1}$, $y_{j,2}$. Otherwise, the approach is defined by $(x_1, y)$ and $(x_2, y)$, and the line continues with $y_j$, $x_{j,1}$, $x_{j,2}$.

For each of the $m$ approaches, print on its own line the minimum protection among the points it can reach that are protected by at least one guard. If none of the points reachable through the approach is protected by a guard, print $-1$.