시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB93363456967.900%

문제

Сергей увлекается цифровой фотографией. Недавно он решил распечатать часть своих снимков и повесить их на стену в прихожей. Для этого он выписал имена файлов всех фотографий и пронумеровал их в порядке появления в этом списке.

Номер Имя файла
1 idx1001.jpg
2 idx1000.jpg
3 idx1014.jpg

После этого Сергей несколько часов выбирал лучшие фотоснимки. Обычно Сергею нравилось сразу несколько подряд идущих фотографий, поэтому он выписывал номер первой и последней из них. В итоге у него получился список интервалов номеров понравившихся ему фотографий.

Номер первой фотографии Номер последней фотографии Имена соответствующих файлов
2 3 idx1000.jpg idx1014.jpg
1 2 idx1001.jpg idx1000.jpg

Теперь Сергей хочет получить список имен файлов всех понравившихся ему фотографий. В этом списке сначала должны быть перечислены в порядке возрастания номеров имена файлов фотографий из первого интервала, затем из второго и т.д.

Имена файлов
idx1000.jpg
idx1014.jpg
idx1001.jpg
idx1000.jpg

Этот список может быть очень большим, поэтому Сергей просит вас ему помочь.

입력

Первая строка входного файла содержит целое число $n$ --- число фотографий ($1 \le n \le 1000$). Следующие $n$ строк содержат имена файлов фотографий, состоящие из строчных и прописных латинских букв, цифр и символов <<\_>> и <<.>>. Длины имен файлов не превышают 100 символов. Следующая строка содержит $m$ --- число интервалов номеров фотографий ($1 \le m \le 1000$). Следующие $m$ строк содержат по два целых числа $l_i$ и $r_i$ --- номер первой и последней фотографии в $i$-м интервале ($1 \le l_i \le r_i \le n$).

출력

Выведите искомый список, по одному имени файла на строке.

예제 입력 1

3
idx1001.jpg
idx1000.jpg
idx1014.jpg
2
2 3
1 2

예제 출력 1

idx1000.jpg
idx1014.jpg
idx1001.jpg
idx1000.jpg