징크스와 평화유지군 캠프

징크스가 평화유지군 캠프를 공격할 계획을 세운다.

캠프는 좌표 평면 위의 영역이다.

캠프에는 평화유지군 경비병이 $n$명 있다. 경비병 $i$는 힘 $v_i$를 가지며, 평면 위의 직사각형 하나를 담당한다. 각 직사각형은 왼쪽 위 점 $(x_1, y_1)$과 오른쪽 아래 점 $(x_2, y_2)$로 주어지며, $x_1 \leq x_2$, $y_1 \leq y_2$이다. 점 $(x, y)$는 $x_1 \leq x \leq x_2$이고 $y_1 \leq y \leq y_2$이면 그 직사각형을 담당하는 경비병의 보호를 받는다.

캠프의 한 점은 여러 경비병의 보호를 받을 수 있고, 담당 직사각형끼리 겹칠 수도 있다. 안타깝게도 징크스에게는 이것이 별로 도움이 되지 않는다. 점 $(x, y)$의 방어력 $s_{x,y}$는 그 점을 지키는 경비병들 가운데 가장 작은 힘과 같다.

캠프에는 $m$개의 접근로가 있다. $j$번째 접근로는 두 직사각형 중 하나 안의 모든 점으로 이어진다. 하나는 꼭짓점이 $(x, y_1)$과 $(x, y_2)$인 직사각형이고, 다른 하나는 꼭짓점이 $(x_1, y)$와 $(x_2, y)$인 직사각형이다. 세로 접근로를 고르면 $\overline{x} = x$이고 $y_1 \leq \overline{y} \leq y_2$인 점 $(\overline{x}, \overline{y})$에 도달할 수 있다. 가로 접근로를 고르면 $\overline{y} = y$이고 $x_1 \leq \overline{x} \leq x_2$인 점에 도달할 수 있다.

각 접근로에 대해, 그 접근로로 도달할 수 있는 점 가운데 경비병이 적어도 한 명 지키는 점들의 방어력 $s_{\overline{x},\overline{y}}$ 최솟값을 구한다.

첫 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \leq n \leq 3 \cdot 10^4$, $1 \leq m \leq 10^5$). 경비병의 수와 접근로의 수이다.

다음 $n$개 줄은 경비병 정보이다. $i$번째 줄에는 다섯 정수 $x_{i,1}$, $x_{i,2}$, $y_{i,1}$, $y_{i,2}$, $v_i$가 주어진다. 앞의 네 값은 경비병 $i$의 직사각형 왼쪽 위 점과 오른쪽 아래 점의 좌표이고, $v_i$는 그 경비병의 힘이다 ($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$).

다음 $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$을 출력한다.