Дано два масиви. Відсортуйте перший з них, а потім для кожного з елементів другого масиву знайдіть, чи зустрічається він у відсортованому першому масиві, і якщо зустрічається, то в якому діапазоні індексів (нумерація починається з 1).

Вхідні дані

1-й рядок містить єдине число ~N~ (~1 \leqslant N \leqslant 123456~) — кількість елементів 1-го масиву. 2-й рядок містить ~N~ розділених пропусками (пробілами) чисел — елементи цього масиву. Серед елементів можуть бути однакові. Не менш ніж третина балів припадає на тести, де цей масив задано вже відсортованим за неспаданням, але у решті тестів це не так.

3-й рядок містить єдине число ~M~ (~1 \leqslant M \leqslant 123456~) - кількість елементів 2-го масиву. 4-й рядок містить ~M~ розділених пропусками (пробілами) чисел - елементи цього масиву.

Значення елементів обох масивів є цілими числами, що не перевищують за модулем ~10^9~ (мільярд).

Результати

Виведіть у один рядок через пропуски (пробіли) рівно ~M~ рядків чисел, кожен з яких містить або єдине число 0 (якщо відповідне число 2-го масиву не зустрічається у 1-му масиві), або два розділені пробілом числа через пропуск (пробіл): індекс першого та індекс останнього входжень відповідного числа 2-го масиву у відсортований вигляд 1-го масиву. 2-й масив сортувати не слід, відповіді повинні бути для того 2-го масиву, який задано у вхідних даних.

Приклади

Ввід

7
17 7 17 42 7 17 7
3
17 42 23

Вивід

4 6
7 7
0

Примітки

Відповідь 4 6 означає, що число 17 зустрічається на 4-й, 5-й та 6-й позиціях відсортованого вигляду 1-го масиву. Відповідь 7 7 — що число 42 зустрічається лише на 7-й позиції. Відповідь 0 - що число 23 взагалі не зустрічається.