Trout
Output: Standard Output (stdout)
Memory limit: 256 megabytes
Time limit: 2.0 seconds
As the director of the Newfound Zealous Irradiating Corporation (NZIC) it has recently come to your attention that there is a significant amount of nuclear waste that you need to dispose of inconspicuously in the local river. Naturally, this will negatively affect the trout population. Thus, it is your job to write a program to help find where the best places are along the river to dump nuclear waste.
The river flows from the source located at point 0, and is described as N points numbered from 0 to N  1 with N  1 flows indicating that the river flows from point a_i to point b_i and has length of w_i metres. This river is somewhat peculiar, in that it can split into multiple streams, but two streams will never join together. It goes without saying of course that every point in the river is reachable from the source at point 0, and the river will never loop back on itself.
At the beginning of your surveying process, you know that there are M trout in the river, and each trout starts off at a point L_i and can swim a maximum distance of S_i before it gets tired. These trout are trying to migrate towards point 0 (to avoid upstream nuclear waste) and so will only swim upstream and never downstream. During your surveying process, you will have to process two types of events. You will either be required to answer a query about the maximum number of trout that could be found at point q or will be informed of a previously undiscovered trout at location x with a maximum swimming distance of y metres. It is possible that preliminary surveying has confirmed all the trout, so you will be given in advance either U = 0 if no new trout will be discovered and U = 1 if new trout may be discovered.
Hopefully through your surveying process you can safely dump your nuclear waste and avoid negatively affecting the trout population.
Input
The first line contains N, M, K, U separated by spaces. That is, the number of points along the river, the number of initially known trout, the number of events to process, and whether new trout may be discovered.
The next N  1 lines each contain three space separated integers a_i, b_i and w_i which indicate that the river flows from point a_i to point b_i and is w_i metres long.
The next M lines each contain two space separated integers, L_i and S_i which is the initial location and the maximum swimming distance of each trout known at the start of surveying.
The final K lines will each contain one of two events, marked D or Q:
 Q \space q indicating a query for the maximum number of trout at point q.
 D \space x \space y indicating a discovery of a new trout at point x with maximum swimming distance of y metres.
Output
Output one line per event of type Q, with the maximum number of trout that could be found at point q based on the trout initially given and any trout discovered before.
Constraints
 2 \leq N \leq 100,000
 1 \leq M, K, \leq 100,000
 0 \leq a_i, b_i < N and 1 \leq w_i \leq 10,000 for all 0 \leq i < N  1
 0 \leq L_i < N and 0 \leq S_i \leq 10^{9} for all 0 \leq i < M
 U = 0 or U = 1, and when U = 0 there will only be Q type events.
 For all events 0 \leq q, x < N and 0 \leq y \leq 10^9
Subtasks
 Subtask 1 (+10%): U = 0 and N, M, K \leq 1,000 and w_i = 1, a_i = i, b_i = i + 1 for 0 \leq i < N  1. That is, there are also no new trout discoveries and the river flows from point 0 through to point N  1 in a line, and every segment is 1 metre long.
 Subtask 2 (+15%): N, M, K \leq 1,000
 Subtask 3 (+20%): U = 0 and a_i = i and b_i = i + 1 for 0 \leq i < N  1. That is, there are no new trout discoveries and the river flows from point 0 through to point N  1 in a line.
 Subtask 4 (+20%): a_i = i and b_i = i + 1 for 0 \leq i < N  1.
 Subtask 5 (+25%): U = 0
 Subtask 6 (+10%): No additional constraints.
Sample explanation
Sample 1
We are given that there are 6 points along the river, 4 initially known trout, 6 events to process, and U = 0 indicating that no new trout will be discovered. The first trout starts at point 5 and could swim up to 2 metres, so it could be found at points 3, 4, or 5. The second trout starts at point 3 and could swim up to 4 metres, so it could be found at points 0, 1, 2, or 3. The third trout starts at point 5 and could swim up to 4 metres, so it could be found at points 1, 2, 3, 4, or 5. The final trout starts at point 2 and could swim up to 2 metres, so it could be found at points 0, 1, or 2. This sample meets the constraints of all subtasks.
Sample 2
This sample meets the constraints of subtasks 2, 5, and 6.
Sample 3
This sample meets the constraints of subtasks 2 and 6.
Note
If you are using Python, select Python 3.6 (PyPy 7.3)
when submitting. Otherwise, your solution may not pass the time limit even if it is maximally efficient.

Sample Input 1
6 4 6 0 0 1 1 1 2 1 2 3 1 3 4 1 4 5 1 5 2 3 4 5 4 2 2 Q 0 Q 1 Q 2 Q 3 Q 4 Q 5
Sample Output 1
2 3 3 3 2 2

Sample Input 2
6 5 4 0 3 4 7 0 3 1 5 1 3 3 2 2 0 5 2 4 3 1 6 0 3 5 2 2 2 Q 0 Q 5 Q 3 Q 0
Sample Output 2
3 2 1 3

Sample Input 3
9 4 8 1 3 8 3 1 2 1 4 7 3 3 5 2 0 4 1 4 3 5 3 1 1 1 6 2 7 0 6 7 5 3 8 11 Q 5 Q 4 D 5 8 Q 4 Q 3 D 2 6 Q 1 Q 0
Sample Output 3
1 1 2 4 2 2