You are implementing the color adjustment feature for a high-performance image editing software. On a $10^9 \times 10^9$ pixel canvas, the color of a pixel at coordinates $(x, y)$ can be represented by an integer in $[0, 9]$.

Users can create multiple layers of color filters. The input to the first layer is the original image, and the input to each subsequent layer is the output of the previous layer. Assuming the user has created a total of $n$ layers of color filters, the final rendered result is the output of the $n$-th layer.

When creating a new layer of color filter, the user defines a rectangular mask on the canvas. The colors outside the mask remain unchanged, and only the colors within the mask are adjusted. Specifically, the user specifies $x_l, x_r, y_l, y_r$ and sets the color lookup table $f_0, f_1, \dots, f_9$ ($0 \le f_i \le 9$) for that layer. For a pixel at coordinates $(x, y)$ with an input color $c$: If $x \in [x_l, x_r]$ and $y \in [y_l, y_r]$, its output color is $f_c$. Otherwise, its output color is $c$.

For usability, the software constrains the rectangular regions of any two layers to be either nested (one contained within the other) or disjoint.

Given the configuration of $n$ color filter layers, write a program to calculate the output for $q$ rendering requests. Each request provides $x, y, c$, and you need to calculate the final output color of a pixel at coordinates $(x, y)$ with an initial color $c$ after passing through these $n$ layers. Note that different requests may provide the same coordinates.

Input

The first line contains two positive integers $n, q$ ($1 \le n \le 5 \times 10^4, 1 \le q \le 2 \times 10^5$), representing the number of color filter layers and the number of requests, respectively.

The next $n$ lines each begin with four positive integers $x_{l,i}, x_{r,i}, y_{l,i}, y_{r,i}$ ($1 \le x_{l,i} < x_{r,i} \le 10^9, 1 \le y_{l,i} < y_{r,i} \le 10^9$), representing the mask range of the $i$-th layer; followed by 10 integers $f_{i,0}, f_{i,1}, \dots, f_{i,9}$ ($0 \le f_{i,j} \le 9$), describing the color lookup table for the $i$-th layer.

The input guarantees that for any two rectangular regions corresponding to color filter layers, their relationship is either nested or disjoint. Furthermore, it is guaranteed that all elements in the set $\{x_{l,1}, x_{l,2}, \dots, x_{l,n}, x_{r,1}, x_{r,2}, \dots, x_{r,n}\}$ are distinct, and all elements in the set $\{y_{l,1}, y_{l,2}, \dots, y_{l,n}, y_{r,1}, y_{r,2}, \dots, y_{r,n}\}$ are distinct.

The next $q$ lines each contain three integers $x, y, c$ ($1 \le x, y \le 10^9, 0 \le c \le 9$), describing each rendering request in order.

Output

Output $q$ lines. For each request, output a single integer representing the final color after passing through the $n$ layers of color adjustment.

Examples

Input 1

4 6
3 6 4 7 3 3 3 3 4 5 6 7 8 9
1 9 1 9 0 0 1 1 2 2 3 3 4 4
7 8 5 8 9 8 7 6 5 4 3 2 1 0
13 15 2 6 7 7 7 7 7 7 8 8 9 9
1 1 5
3 4 2
6 7 8
8 6 2
10 3 7
14 2 6

Output 1

2
1
4
8
7
8