C. Viruses
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

We're trying to install $$$n$$$ Odoo modules from your local machine to the server.

Imagine that the path from your local machine to the server is a line where your machine is at position $$$0$$$ and the server is at position $$$k$$$ ($$$k = 10^{9}$$$, fixed).

Initially, each module has:

  • An initial position between $$$0$$$ and $$$k-1$$$
  • An initial capacity to resist viruses.

Each second, the module advances $$$1$$$ unit (its position advances by $$$1$$$).

You started the installation, and all your modules were moving to the server, but someone introduced $$$m$$$ viruses in different positions of the line in the opposite direction of the installation (right to left) (Viruses move with the same speed).

Each virus has different capacities to impact each module. It can have capacity $$$X$$$ against module $$$A$$$ and capacity $$$Y$$$ against module $$$B$$$.

When a module and a virus collide (touch each other at any part of the line):

  • If the virus does not have any capacity against this specific module, nothing happens (the module continues its path to the server, and the virus continues its path to the left looking for a module to kill).
  • If the virus does have capacity against this module, the one with lower capacity is removed. If the module survives, its capacity decreases by the virus capacity against it. Yes, you're right! If they both have the same capacity, they are both removed.
A module can only fight against a virus coming from its right, and a virus can only fight against a module coming from its left.
Input

The first line contains $$$3$$$ integers $$$n$$$, $$$m$$$, and $$$q$$$ $$$(1 \leq n \leq 10^{3}, 1\leq m \leq 5\cdot 10^{3}, 0 \leq q \leq 5\cdot 10^{5})$$$ denoting the number of modules, the number of viruses, and the number of the capacities of viruses against modules.

Each of the following $$$n$$$ lines contains $$$module_{i}$$$, $$$capacity_{i}$$$, and $$$modulePosition_{i}$$$ ($$$module_{i}$$$ is a string, $$$1\leq length(module_{i}) \leq 20$$$, $$$1 \leq capacity_{i} \leq 10^{5}$$$, $$$0 \leq modulePosition_{i} \leq k-1$$$) denoting the name of the $$$i_{th}$$$ module, its capacity, and its initial position. It's guaranteed that there is no space in the name of the module, and no two modules have the same name. It's also guaranteed that no two modules have the same position.

Each line in the $$$m$$$ following lines contains $$$virus_{i}$$$ and $$$virusPosition_{i}$$$ ($$$ 1 \leq virus_{i} \leq m$$$, $$$0 \leq virusPosition_{i} \leq k-1$$$) denoting the $$$ID$$$ of the virus followed by its initial position. It's guaranteed that no two viruses have the same $$$ID$$$. It's also guaranteed that no two viruses have the same position.

Each line in the $$$q$$$ following lines contains $$$virus_i$$$, $$$module_i$$$, $$$capacityAgainst_i$$$ $$$(1\leq virus_i \leq m, 1\leq capacityAgainst_i \leq 10^5)$$$ denoting the $$$ID$$$ of the virus followed by the name of the module and its capacity against that module. It's guaranteed that $$$module_i$$$ exists in the list of modules. It's guaranteed that every pair of virus and module pair appears at most one time.

If a module and virus exist in the same position at the beginning, they collide.

Output

Print the number of modules remaining in the first line. Print the names of the remaining modules sorted by arrival time in increasing order in the second line separated by spaces.

Example
Input
5 3 7
Project 5 0
Time-Off 1 70
To-do 80 4
Timesheets 10 10
Employees 2 40
1 15
2 50
3 60
1 Time-Off 100
1 Employees 200
2 To-do 84
2 Project 4
3 Employees 4
3 To-do 50
3 Project 2
Output
2
Time-Off Timesheets