Problem Background

To protect fish populations, only the most skilled fishermen are allowed to continue fishing in Dongting Lake. After rigorous selection, only the solitary fisherman in a lonely boat remains. Previously, he fished, played cards, and practiced martial arts with other fishermen, but now he is alone, and the fisherman cannot help but feel melancholy. Those who were eliminated from the selection have likely returned home to farm and raise pigs.

Problem Description

The fisherman is currently practicing a martial art called "Mutual Combat Technique," which is said to have been首创 by Zhou Botong.

During practice, the fisherman's hands move within a vertical plane. Taking a point in this plane as the origin, the positive x-axis points to the right, and the positive y-axis points upward, forming a Cartesian coordinate system. A point in this plane can be represented by coordinates \((x, y)\).

The technique has \(n\) pause points, denoted as \(p_1 = (x_1, y_1), p_2 = (x_2, y_2), \ldots, p_n = (x_n, y_n)\). The practice process can be divided into one-second intervals. At the \(i\)-th second, both hands are at pause points. At the end of the \(i\)-th second, the hands move to other pause points (or may remain stationary).

There are \(k\) special moves in the Mutual Combat Technique. The \(i\)-th move is: when the left hand is at the \(v_i\)-th pause point and the right hand is at the \(u_i\)-th pause point, the move can be executed.

There are also禁忌 in practicing the martial art. If the Manhattan distance between the two hands is less than \(d_{min}\) during a pause, it can lead to走火入魔. If the Manhattan distance is greater than \(d_{max}\), the fisherman's arms are clearly being stretched to the breaking point. Therefore, if the left hand is at the \(l\)-th pause point and the right hand is at the \(r\)-th pause point, it must satisfy \(d_{min} \leq |x_l - x_r| + |y_l - y_r| \leq d_{max}\).

Moving from one pause point to another has its own rules, and they differ for the left and right hands. There are \(m\) movement conditions, each condition being: the left hand can move from the \(a\)-th pause point to the \(b\)-th pause point and vice versa, or the right hand can move from the \(a\)-th pause point to the \(b\)-th pause point and vice versa. For each second, the fisherman's hands are not fast enough, so each hand can move at most once. Any movement not mentioned above is illegal.

The fisherman hopes to execute a combo. That is, after executing the \(i\)-th move, after \(t\) seconds of movement, execute the \(j\)-th move, where \(i \neq j\).

Given \(p_1, \ldots, p_n\), \(v_1, \ldots, v_k\), \(u_1, \ldots, u_k\), \(d_{min}\), \(d_{max}\), and \(m\) movement conditions, the fisherman wants to know, after executing the \(i\)-th move, the minimum number of seconds required to execute a move with a different编号, i.e., the shortest time to execute a combo. Please output the answer for each \(1 \leq i \leq k\).

Input Format

The first line contains two positive integers \(n, m\).

The second line contains two non-negative integers \(d_{min}, d_{max}\). It is guaranteed that \(d_{min} \leq d_{max}\).

The next \(n\) lines, the \(i\)-th line contains two positive integers \(x, y\) representing the coordinates of the \(i\)-th pause point.

The next line contains a positive integer \(k\).

The next \(k\) lines, the \(i\)-th line contains two positive integers \(v, u\) representing the \(i\)-th move. The left hand is at the \(v\)-th pause point, and the right hand is at the \(u\)-th pause point to execute the move. It is guaranteed that \(1 \leq v, u \leq n\), no two moves are identical, and the Manhattan distance between \(v, u\) is not less than \(d_{min}\) and not greater than \(d_{max}\).

The next \(m\) lines, each line contains three positive integers \(a, b, type\). If \(type = 0\), it means the left hand can move from the \(a\)-th pause point to the \(b\)-th pause point and vice versa. If \(type = 1\), it means the right hand can move from the \(a\)-th pause point to the \(b\)-th pause point and vice versa. It is guaranteed that \(1 \leq a, b \leq n\), \(type \in \{0, 1\}\).

Output Format

\(k\) lines, the \(i\)-th line represents the shortest time to execute a combo after the \(i\)-th move.

If it is impossible to execute a combo, output \(-1\).

Sample Input and Output

Input Sample #1

5 5
1 6
3 2
9 2
7 3
7 8
4 9
3
5 4
1 3
1 2
1 2 0
2 5 0
1 5 1
1 3 1
3 4 1

Output Sample #1

2
2
-1

Input Sample #2

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

Output Sample #2

2
1
1
-1

Notes

[Sample Explanation]

Explanation for Sample One For move 1, the left hand can first move to pause point 2 and the right hand to pause point 3, taking 1 second, then the left hand moves to pause point 1 and the right hand remains stationary, allowing move 2 to be executed, totaling 2 seconds. For move 2, the process can be reversed to execute move 1. For move 3, the right hand cannot move, so no move can be executed, hence output \(-1\).

Explanation for Sample Two Not explained.

[Data Constraints]

20% of the data, \(n \leq 50\), \(m \leq 100\), \(k \leq 100\).
Another 30% of the data, \(n \leq 500\), \(m \leq 2000\), \(k \leq 10000\), \(d_{min} = 0\), \(d_{max} = 10000\).
For 100% of the data, \(n \leq 1000\), \(m \leq 4000\), \(1 \leq x_i, y_i \leq 1000\), \(0 \leq d_{min} \leq d_{max} \leq 10^9\).

见题面 Input 部分

见题面 Output 部分