Burst Balloons and Happy Children

On Children’s Day, SHUXK is forced to play a boring game with m kids. There are n boxes arranged from left to right, with the i-th box containing a_i balloons. SHUXK will perform Q operations. In each operation, he selects one unburst balloon from a specified box; immediately after, the kids burst that balloon.

Each of the m children has chosen an interval of boxes \([l_i, r_i]\). A child becomes happy at the moment when he finds that all the balloons in his interval have been burst (and remains happy thereafter). After each operation, determine how many children are happy so far.

Note: If an operation targets a box that already has no available balloon, nothing happens.

inputFormat

The first line contains three integers n, m and Q \( (1 \leq n, m, Q \leq \text{large}) \), representing the number of boxes, the number of children, and the number of operations respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) where \(a_i\) is the number of balloons in the \(i\)-th box.

The following \(m\) lines each contain two integers \(l_i\) and \(r_i\) \((1 \leq l_i \leq r_i \leq n)\), describing the interval of boxes chosen by the \(i\)-th child.

The next \(Q\) lines each contain one integer \(x\) \((1 \le x \le n)\), indicating that in that operation, SHUXK selects one unburst balloon from the \(x\)-th box. It is guaranteed that when an operation is performed, if the \(x\)-th box still has unburst balloons, one of them is removed.

outputFormat

Output \(Q\) lines. The \(i\)-th line should display the total number of children who are happy after the first \(i\) operations.

sample

5 2 6
1 1 1 1 1
1 3
3 5
1
2
3
4
5
3

0
0
1
1
2
2