Rides 1

There are $N$ children numbered from 1 to $N$. The children love going to the amusement park, but height limits often keep them off the rides. There are $M$ rides numbered from 1 to $M$, and every ride holds exactly 2 people. Children $i$ and $j$ can ride ride $k$ together only if (height of child $i$) + (height of child $j$) $\ge$ (height limit of ride $k$).

You are given $Q$ triples $(i, j, k)$. Each triple means that children $i$ and $j$ try to ride ride $k$ every day. $i$ and $j$ may be equal, and the same formula applies in that case. If the same triple appears several times, each copy counts separately.

At the start every child is 0 cm tall, so nobody can ride anything. The children are growing fast, though.

On each day from day 1 to day $K$, exactly one child grows by 1. Given which child grows on each day, write a program that finds, 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 first and the rides happen after it.

The first line contains the number of children $N$, the number of rides $M$, the number of days $K$, and the number of triples $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: the child who grows on each day, in order of days. ($1 \le$ child 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$)

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

In the first example, nobody can ride anything on days 1 and 2.

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

On day 4, children 3 and 5 can ride ride 3, and children 1 and 2 can ride ride 2.