Rides 2

There are N children numbered 1 to N. They love going to the amusement park, but height limits often keep them off the rides. There are M rides numbered 1 to M, and every ride seats exactly 2 people.

For child i and child j to ride ride k together, (height of child i) + (height of child j) ≥ (height limit of ride k) must hold.

You are given Q triples (i, j, k). Each triple means that child i and child j try to ride ride k every day. All children start at a height of 0 cm, so at first nobody can ride anything. The children are in a growth spurt, though. Specifically, on each day from day 1 to day K, one child grows by 1.

In this problem the children grow alarmingly fast! If the number of rides the children took on the previous day is greater than the number of rides they took on the day before that, the child grows by 2 that day instead of 1. This rule does not apply on day 1 or day 2.

Given which child grows on each day, write a program that prints, for each day from day 1 to day K, the total number of rides the children take that day. Within a day, the growth happens before the rides.

The first line contains the number of children N, the number of rides M, the number of days K, and the number of queries Q. ($1 \le N, M, K, Q \le 200{,}000$)

The second line contains the height limits of rides 1 to M in order. ($1 \le$ height limit $\le 200{,}000$)

The third line contains K numbers: for each day from day 1 to day K, the number of the child who grows that day. ($1 \le$ number $\le N$)

Each of the next Q lines contains one triple (i, j, k). ($1 \le i, j \le N$, $1 \le k \le M$) i and j may be equal; in that case the condition is (height of child i) + (height of child i) ≥ (height limit of ride k).

Print K lines. Line d is the total number of rides the children take on day d.

Up to day 2, no child can ride anything.

On day 3, children 3 and 5 can ride ride 3.

On day 4, children 3 and 5 can ride ride 3, children 1 and 2 can ride rides 1 and 2, and children 1 and 5 can ride ride 2. The count on day 3 (1) is greater than the count on day 2 (0), so child 1 grows by 2 on day 4.