The data analysts at Spotify have calculated the top ~k~ songs for two people, person ~A~ and person ~B~. For each song, they also computed a preference score, representing how much that person likes the song.

Given this data, you, an engineer at Spotify, are tasked with creating a 'blended' playlist with exactly ~n~ songs, as follows:

Each person must contribute exactly ~\frac{n}{2}~ songs to the blend. ~n~ is guaranteed to be even.

For any song ~i~:

• ~a_i~ is ~A~'s preference score for song ~i~
• ~b_i~ is ~B~'s preference score for song ~i~

If a song does not appear in one person's top-~k~ list, that person's preference score for the song is considered to be ~0~.

A song ~i~ can be contributed by person ~A~ only if ~a_i \geq b_i~ and by person ~B~ only if ~b_i\geq a_i~. Thus, if preference scores are equal, the song may be contributed by either person.

The overall score of song ~i~ if it were in the blended playlist is ~a_i+b_i~. The score of the playlist is the sum of these scores of all selected songs. You are tasked with finding a blended playlist that maximises the total score so you can satisfy both people, as well as your manager.

Input

The first line contains two integers, ~n~ and ~k~ ~(1 \leq n, k\leq 10^5)~. We additionally have that ~n \leq 2k~, and ~n~ must be even.

The next ~k~ lines contain the top-~k~ list of person ~A~. Each of the next ~k~ lines contain a string ~S_i~ ~(1 \leq |S_i| \leq 20)~ and an integer ~a_i~ ~(1 \leq a_i \leq 10^9)~, representing the name of the song and the preference score of that song. The song name consists only of upper and lowercase English characters, and digits ~0~-~9~. The song names are unique within each persons top-~k~ list. These lines are given in decreasing order of ~a_i~.

The next ~k~ lines are given in the same format, but represent the top-~k~ list of person ~B~.

Output

Output any valid blend with exactly ~n~ songs (in any order) such that each song appears at most once, exactly ~\frac{n}{2}~ songs are contributed by person ~A~, exactly ~\frac{n}{2}~ songs are contributed by person ~B~, and the total playlist score is maximized. If it is impossible to construct a valid blend, output -1.

Specifically, you should output ~n~ lines, where each line is of the form song_i contributor. song_i is the song name, and contributor is who contributes the song (it should be a single character A or B).

Example

Input 1

2 2
despacito 5
gangnamstyle 3
baby 4
despacito 1

Output 1

despacito A
baby B

The blended playlist needs ~1~ song from ~A~ and ~1~ song from ~B~. The best choice is despacito contributed by ~A~ (score ~5+1=6~) and baby contributed by B (score ~0+4=4~), for a total of ~6+4=10~.

Input 2

4 3
good4u 5
airplanes 4
ghostbusters 1
good4u 5
peaches 4
disturbia 1

Output 2

good4u A
airplanes A
peaches B
disturbia B

We need 2 songs from each person. Here good4u has equal scores, so it can be contributed by either ~A~ or ~B~. The shown blend has total score ~10+4+4+1=19~. Other optimal blends are possible, including swapping who contributes good4u, or simply reordering the output lines, as long as the same multiset of songs and contributors is valid.

Input 3

6 4
aa 9
bb 8
cc 7
dd 1
bb 10
cc 7
ee 6
ff 2

Output 3

aa A
cc A
dd A
bb B
ee B
ff B

We need 3 songs from each person. cc is the only song that can go either way; to reach 3 songs from A, it must be contributed by A. The total score is ~9+14+1+18+6+2=50~ (each term is ~a_i+b_i~). Other valid outputs can reorder the lines but must keep the same contributor assignment for cc to stay feasible.

Input 4

4 4
Hello 5
RIPMyGranny 4
Cupid 4
Phonk 2
RIPMyGranny 3
Hello 2
Cupid 1
Goodbye 1

Output 4

-1

It is impossible for each person to contribute ~2~ songs, as three songs are shared between both people and person ~A~ has a higher preference score for all three of them, so person ~B~ is only able to contribute a single song — Goodbye.