As a TA, Lauren uses a lot of whiteboard markers. She has a collection of ~n~ markers in ~k~ different colours. Each marker ~1 \le i \le n~ has a particular amount of ink left, ~x_i~, and has a particular colour, ~c_i~.

Since whiteboard markers get worse as they run out of ink, when choosing a whiteboard marker of a particular colour to use next, Lauren always wants to choose the one with the most amount of ink first. If there are multiple markers of that colour with the greatest amount of ink, she will choose the marker with the lower index. After using a marker, it will consume some amount of ink.

More precisely, after Lauren uses ~y~ units of ink from marker ~i~, the new value of ~x_i~ will be ~x_i - y~. If there are no markers of the desired colour with enough ink left, she will not use any marker (and will be sad). Note that Lauren can only use one marker at a time.

Help Lauren determine which marker to use, given the colour and amount of ink she needs to use.

Input

Your first line will contain ~n~ and ~m~ as space-separated integers, representing the number of whiteboard markers Lauren has the number of queries she will make.

Your next ~n~ lines will contain an integer ~x_i~ and a string ~c_i~, separated by a space, representing the amount of ink left in the ~i~th marker and the colour of the ~i~th marker respectively.

Your next ~m~ lines will contain an integer ~y_j~ and a string ~d_j~, separated by a space, representing that Lauren needs to use ~y_j~ units of ink of colour ~d_j~.

Output

For each query, output the index (~i~) of the marker that Lauren should use. If there are no markers of the desired colour with enough ink left, output ~0~.

Constraints

• ~1 \le k \le 10~
• ~1 \le x_i, y_j \le 1000~ for all ~1 \le i \le n~ and for all ~1 \le j \le m~

Subtask 1

• ~1 \le n \le 500~
• ~1 \le m \le 500~

Subtask 2

• ~1 \le n \le 10^5~
• ~1 \le m \le 10^5~

Example 1

Input

7 9
10 black
8 blue
5 black
10 black
9 blue
4 red
3 red
2 blue
10 black
3 blue
10 black
6 black
3 red
2 red
1 red
2 red

Output

5
1
2
4
0
6
7
6
0

Explanation

The initial whiteboard markers are:

10 black
8 blue
5 black
10 black
9 blue
4 red
3 red

The queries are:

2 blue
10 black
3 blue
10 black
6 black
3 red
2 red
1 red
2 red

• The output of query 1, 2 blue, is 5. There are 2 blue markers, marker 2 with 8 ink and marker 5 with 9 ink, so we choose marker 5. Marker 5 now has 7 ink remaining.
• The output of query 2, 10 black, is 1. There are 3 black markers, marker 1 with 10 ink, marker 3 with 5 ink, and marker 4 with 10 ink. Markers 1 and 4 both have 10 ink, so we choose the one with the lower index, marker 1. Marker 1 now has 0 ink remaining.
• The output of query 3, 3 blue, is 2. There are 2 blue markers, marker 2 with 8 ink and marker 5 with 7 ink, so we choose marker 2. Marker 2 now has 5 ink remaining.

Example 2

Input

1 3
10 black
1 black
10 black
1 black

Output

1
0
1

Explanation

• The output of query 1, 1 black, is 1. The only black marker has 10 ink. Marker 1 now has 9 ink remaining.
• The output of query 2, 10 black, is 0. The only black marker only has 9 ink, which is not enough, and no markers are used. Marker 1 still has 9 ink remaining.
• The output of query 3, 1 black, is 1. The only black marker has 9 ink. Marker 1 now has 8 ink remaining.

Example 3

Input

1 1
10 black
1 blue

Output

0

Explanation

• The output of query 1, 1 blue, is 0. There are no blue markers in the collection, so we cannot use any markers.