Файлы

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

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

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

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

Первая строка входного файла содержит целое число $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$).

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