Giải bài trực tuyến

The language of an ancient tribe was only based on two characters - a and b - to create words. It also used character space to separate words in the sentence. So, a word was an unextendible consecutive characters in a sentence. A sentence did not contain meaningless words. People in the tribe were very religious, they believed that each word had its own lucky value. The value of a sentence is the summation of the value of each word in that sentence.

You can use at most x character a, y character b and z character space to make the a sentence. Show us how lucky you are! Tell us the luckiest sentence you can make. In case of multiple solutions, print the smallest lexicographical sentence (space is smaller than a and a is smaller than b).

Input

• The first line contains N, the number of meaningful words in the language.(1 ≤ N ≤ 50)
• The second line contains 3 integer numbers:x, y, z as stated.( 0 ≤ x, y, z ≤ 50)
• Each of the next N lines contains one word and its value, separated by a space. Value of a word is a positive integer and not exceed 50.

Output

Only one line, contains the sentence you found.

Example

Input:
4
3 3 1
abb 3
baa 3
aaa 4
bbb 1

Output:
abb baa

Note

• The sentence s1 is lexicographically smaller than sentence s2 if the string represents s1 is smaller than s2.