До кладошукача Степана потрапила карта стародавнього підземелля. Підземелля має форму лабіринту розміру 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).

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

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

В першому рядку виведіть одне число - довжину найкоротшого шляху.
В наступних рядках необхідно вивести найкоротший маршрут. Кожну клітинку маршрута (включно з початковою та кінцевою) вивести в окремому рядку в форматі xi yi, де xi - рядок клітинки, а yi - стовпець клітинки.

Якщо існує декілька шляхів мінімальної довжини, виведіть будь-який.
Якщо до скарбу неможливо дістатись, виведіть в єдиному рядку -1.

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

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

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

4
1 1
1 2
1 3
2 3
3 3

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

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

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

-1