During the cherry blossom season, WHU attracts a large number of tourists, which greatly troubles xuxuxuxuxu. Therefore, he invented a magic button that, when pressed, would make all the tourists on campus exit the school through the nearest open gate at the speed of light. xuxuxuxuxu is now very curious about the sum of the distances traveled by the tourists at each moment as they exit the school at the speed of light.
Specifically, WHU is an undirected graph with $$$n$$$ nodes and $$$m$$$ edges. Each node is occupied by $$$a_i$$$ tourists. Among the $$$n$$$ nodes, $$$k$$$ of them serve as gates, and each gate has an opening time interval $$$[l_i, r_i]$$$. The question is, for each moment from $$$1$$$ to $$$T$$$, what is the sum of the distances traveled by tourists leaving the campus at the speed of light?
Note: If any tourists are unable to exit the school, the sum of the distances should be assumed to be $$$-1$$$.
Guarantee graph connectivity, absence of self-loops, and presence of multiple edges for the given data.
The first line contains four integers $$$n$$$ ($$$1 \le n \le 10^5$$$), $$$m$$$ ($$$1 \le m \le 10^5$$$), $$$k$$$ ($$$1 \le k \le 15$$$), $$$T$$$ ($$$1 \le T \le 10^5$$$).
The Second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^3$$$), representing the number of tourists at the $$$i$$$-th node.
Each of the next $$$k$$$ lines contains three integers $$$p_i$$$ ($$$1 \le p_i \le n$$$), $$$l_i$$$, $$$r_i$$$ ($$$1 \le l_i \le r_i \le T$$$), representing the $$$i$$$-th gate is the node with index $$$p_i$$$ in the graph, and the opening time of the gate is $$$[l_i, r_i]$$$.
Each of the next $$$m$$$ lines contains three integers $$$u,v,w$$$ ($$$1 \le u,v \le n,1 \le w \le 10^3$$$), representing a path of length $$$w$$$ between $$$u$$$ and $$$v$$$.
Print T lines, each containing an integer representing the sum of the distances at the $$$i$$$-th moment.
6 8 3 31 2 3 4 5 64 1 35 1 26 2 21 3 11 2 22 4 23 4 35 1 45 2 31 6 53 6 2
47 13 72
At time moment $$$1$$$, gates at nodes $$$4$$$ and $$$5$$$ are open, while the gate at node $$$6$$$ is closed. One tourist at node $$$1$$$ can choose either node $$$4$$$ or $$$5$$$ to exit, resulting in a total distance of $$$4$$$. Two tourists at node $$$2$$$ can choose node $$$4$$$ to exit, resulting in a total distance of $$$2 \times 2=4$$$. Three tourists at node $$$3$$$ can choose node $$$4$$$ to exit, resulting in a total distance of $$$3 \times 3=9$$$. Four tourists at node $$$4$$$ can choose node $$$4$$$ to exit, resulting in a total distance of $$$0$$$. Five tourists at node $$$5$$$ can choose node $$$5$$$ to exit, resulting in a total distance of $$$0$$$. Six tourists at node $$$6$$$ can choose node $$$4$$$ to exit, resulting in a total distance of $$$6 \times 5=30$$$. The sum of distances for all individuals is $$$4+4+9+0+0+30=47$$$.
