Shopping Cart (APCS 2020-07 Beginner)

You are given two integers \(a\) and \(b\), the product IDs you want to observe.

Each customer's shopping cart has a sensor that records when they add or remove products. The record is a sequence of integers: a positive integer \(x\) means the customer adds a product with ID \(x\) to the cart; a negative integer \(-x\) means the customer removes a product with ID \(x\) from the cart.

There are \(n\) customers' cart records. You want to count how many customers ended up buying both product \(a\) and product \(b\). A customer has bought product \(x\) if it was added to their cart more times than it was removed.

Input

The first line contains two positive integers \(a\) and \(b\).

The second line contains a positive integer \(n\), the number of customers.

The next \(n\) lines each contain the \(i\)-th customer's record: a sequence of integers ending with \(0\) (the end marker); every other number is a non-zero integer with absolute value at most \(100\), as defined above.

Constraints

• \(1 \le a, b \le 100\)
• \(1 \le n \le 100\)
• Except the trailing \(0\), every number in a record is a non-zero integer with absolute value at most \(100\)

Output

Output a single integer: the number of customers who bought both product \(a\) and product \(b\).

Scoring

The time limit for each test case is \(1\) second; your score is the sum over the test cases you pass. The subtasks are:

• Subtask 1 (\(50\) points): every record has exactly \(2\) positive integers followed by a trailing \(0\) (no removals).
• Subtask 2 (\(50\) points): the original constraints.

Sample Input 1

1 8
5
1 8 0
5 6 0
2 7 0
8 1 0
33 22 0

Sample Output 1

2

Sample Input 2

3 9
2
3 9 -3 3 9 0
3 3 -3 -3 9 0

Sample Output 2

1

Source

APCS programming exam, July 2020, Problem 1.

• ZeroJudge f579