Top Salesperson

Time limit1.5sMemory limit1024 MB

Summary

Given each employee's initial sales at their assigned stores, print after each sales record how many employees lead every store they are in charge of.

Level: Medium5 of 10
Topics: Array, Implementation, Simulation
Solved: No attempts yet

Problem

ZerOne Inc. president Jeongmin decides to choose a top salesperson to put some pressure on employees who have gotten complacent. Each employee is in charge of $K$ of the $M$ stores in total. The top salesperson is the employee who holds the first place in cumulative sales at every store they are in charge of. At each store, the cumulative sales amounts of the employees are always distinct and never decrease.

The sales records made by ZerOne employees are given in chronological order. After each record, compute the cumulative sales amounts and find the number of top salespeople.

Input

The first line contains the number of employees $N$ , the total number of stores $M$ , and the number of stores $K$ each employee is in charge of, separated by spaces. ( $1 \le N \le 300$ , $1 \le M \le 10\,000$ , $1 \le K \le M$ )

From the second line, each employee's store number $j$ and initial sales amount $t$ are given $K$ times per line, separated by spaces. The data is given in order from employee 1 to employee $N$ . ( $1 \le j \le M$ , $1 \le t \le 10\,000$ )

The $(N+2)$ -th line contains the number of sales records $Q$ . ( $1 \le Q \le 1\,000\,000$ )

From the $(N+3)$ -th line, $Q$ lines follow in chronological order. Each line contains the employee number $i$ , the store number $j$ , and the amount $v$ added to the cumulative sales at that store, separated by spaces. ( $1 \le i \le N$ , $1 \le j \le M$ , $1 \le v \le 1\,000$ )

All numbers in the input are integers.

Output

After each sales record, print the current number of top salespeople on its own line, for a total of $Q$ lines.

Examples2

Example 1

Input

4 5 2
1 100 4 230
1 80 2 170
2 250 5 280
1 90 3 100
3
2 2 100
4 1 50
2 2 10

Expected output

1
1
1

Example 2

Input

4 5 2
1 100 4 230
1 80 2 170
2 250 5 280
1 90 3 100
3
2 2 70
2 2 20
2 1 30

Expected output

2
1
1