У Риты была строка s, Гоша подарил ей на 8 марта ещё n других строк t_i, 1≤ i≤ n. Теперь Рита думает, куда их лучше поставить. Один из вариантов —– расположить подаренные строки внутри имеющейся строки s, поставив строку t_i сразу после символа строки s с номером k_i (в частности, если k_i=0, то строка вставляется в самое начало s).

Помогите Рите и определите, какая строка получится после вставки в s всех подаренных Гошей строк.

В первой строке дана строка s. Строка состоит из строчных букв английского алфавита, не бывает пустой и её длина не превышает 10⁵ символов. Во второй строке записано количество подаренных строк — натуральное число n, 1 ≤ n ≤ 10⁵. В каждой из следующих n строк через пробел записаны пары t_i и k_i. Строка ti состоит из маленьких латинских букв и не бывает пустой. k_i — целое число, лежащее в диапазоне от 0 до |s|. Все числа k_i уникальны. Гарантируется, что суммарная длина всех строк t_i не превосходит 10⁵.

Выведите получившуюся в результате вставок строку.