До кладошукача Степана потрапила карта стародавнього підземелля. Підземелля має форму лабіринту розміру N×M.

Кожна клітинка лабіринта або пуста і по ній можна пройти, або містить стіну. З клітинки можна переходити тільки в сусідню клітинку (тобто у кожної клітинки є не більше 4 сусідів).

В одній з клітинок знаходиться скарб, який хоче дістати Степан. В лабіринті є K входів, з яких Степан може розпочати свій шлях.

Необхідно визначити, з якого входу Степану необхідно розпочати свій шлях, щоб відстань до скарбу була якомога меншим. Якщо таких входів кілька, необхідно вивести вхід з найменшим номером.

Формат вхідних даних

Перший рядок містить 2 числа N та M - розміри лабіринта. (1≤N,M≤100, N×M≤100)
Далі йде опис лабіринта: N рядків по M символів в кожному. 0 означає, що клітинка вільна; 1 - що в клітинці знаходиться стіна. Символ * позначає клітинку зі скарбом (така клітинка в лабіринті рівно одна).

В (N+2)-му ряду знаходиться число K (1≤K≤N×M) - кількість входів до лабіринту. Далі в K рядках містяться координати входів. Так, в i-му рядку містяться числа xi и yi, які означають, що i-й вхід розташований в xi-му рядку та в yi-му стовпчику (1≤xi≤N,1≤yi≤M).

Гарантується, що координати входів попарно різні, і те що всі входи розташовані в пустих клітинках. Жоден з входів не ннаходиться в клітинці зі скарбом.

Формат вихідних даних

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

Приклад вхідних даних-1

5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5

Приклад вихідних даних-1

1

Приклад вхідних даних-2

3 3
010
1*1
010
4
1 1
1 3
3 1
3 3

Приклад вихідних даних-2

-1