A. Ladies Brunch
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Itzel is very excited because her friend group organized a "ladies brunch" at the new aesthetic restaurant in town: La Cafetería Orgánica De Especialidad: Frappés, Éclairs y Matcha (CODEFEM). She woke up at 9:00, had breakfast at 10:00, went to the gym until 12:00, got ready, and arrived on time at 15:00.

Itzel and her friends sit around a circular table in clockwise order, where Itzel occupies position $$$0$$$ and her friends occupy positions $$$1, 2, \dots, N-1$$$.

The cafe has a menu consisting of $$$M$$$ products with fixed integer prices. As the afternoon progresses, they start ordering drinks and desserts. Seeing that the waitress is overwhelmed by the high volume of orders and is having trouble keeping track of everyone's bill, Itzel decides to write a program to process the orders.

There are $$$Q$$$ operations of three types:

  • 1 PersonName ProductName: The specified person orders a product from the menu.
  • 2 L R ProductName: Everyone seated in the clockwise circular range from position $$$L$$$ to position $$$R$$$ ($$$0 \le L, R \lt N$$$) orders the specified product. If $$$L \le R$$$, this covers positions $$$L, L+1, \dots, R$$$. If $$$R \lt L$$$, this wraps around the circular table, covering positions $$$L, L+1, \dots, N-1$$$ and $$$0, 1, \dots, R$$$.
  • 3 PersonName: The waitress queries the total accumulated bill for the specified person.

Help Itzel process all operations and output the answers to all queries.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 100000$$$, $$$1 \le M \le 10000$$$), the number of people at the table and the number of menu products.

The second line contains $$$N$$$ space-separated strings: the names of the people seated in clockwise order (the first person is Itzel at position $$$0$$$).

The next $$$M$$$ lines each contain a string $$$ProductName$$$ and an integer $$$P$$$ ($$$1 \le P \le 10^9$$$), representing the product name and its price.

All person names are distinct, and all product names are distinct. Every name consists of between $$$1$$$ and $$$20$$$ characters without spaces. The total length of all strings in the input does not exceed $$$10^6$$$.

The next line contains an integer $$$Q$$$ ($$$1 \le Q \le 100000$$$), the number of operations.

The next $$$Q$$$ lines describe the operations in the format specified above.

Output

For each operation of type 3, print a single integer on a new line: the total accumulated bill of the queried person.

Example
Input
4 3
Itzel Celi Emily Sofia
MatchaLatte 85
Eclair 60
TaroFrappe 95
5
1 Itzel MatchaLatte
2 2 0 Eclair
3 Itzel
3 Celi
3 Emily
Output
145
0
60