There are $N$ packets of goods each having some number of items in it. The number of items is in the form of an array $A$ ($A[i]$ items of the $i^{th}$ type). There are $M$ number of people in total each having a share in the goods. They have shares in the form of $L$ and $R$ which means that they hold a share of goods $[L....R]$. You require $Q$ items. You must identify the items one by one.
For each time you take an item, you are required to determine the number of people who have lost all the items from their share.

Note

• You cannot get the items that are not available.
• Here, 'lost all items' means that there are no items left in the share that you hold.

Input format

• First line: An integer $N$ representing the number of goods
• Next $N$ lines: $N$ integers follow representing the number of items of each type of good
• Next line: Two integers $M$ and $2$ where $M$ denotes the number of people 
• Next $M$ lines: Two integers $L$ and $R$ representing their shares
• Next line: An integer $Q$ followed by $Q$ integers representing the goods that you require
  Note: Each integer must be represented in a separate line.

Output format

Print $Q$ space-separated integers representing the number of people who lost all the items of their share.

Constraints

$1 \le N,M,Q \le 10^5$

$1 \le A[i] \le 10^5$

$1 \le L \le R \le N$

All $Q$ integers will be in the range of $1$ to $N$.