Сервер игры «Морской бой» хранит состояние квадратного поля размера n × n, на котором размещены корабли.

Каждый корабль занимает несколько клеток и представляет собой связную по стороне прямую полоску ширины 1: либо горизонтальную, либо вертикальную. Длина корабля может быть от 1 до n. Корабли на поле размещены корректно: клетки разных кораблей не соприкасаются ни по стороне, ни по углу.

Поле задано сеткой:

• '.' — пустая клетка;
• '#' — клетка корабля.

После этого сервер получает q запросов — выстрелов по клеткам поля. Для каждого выстрела нужно определить, какой ответ должен вернуть сервер:

• miss — если выстрел пришёлся в пустую клетку, либо в клетку, по которой уже стреляли ранее;
• hit — если выстрел попал в ещё не подбитую клетку корабля, но после этого у данного корабля осталась хотя бы одна не подбитая клетка;
• sunk — если выстрел попал в ещё не подбитую клетку корабля и уничтожил его последнюю оставшуюся клетку.

Требуется обработать все выстрелы в указанном порядке.

Входные данные

В первой строке задано одно целое число n — размер поля.

В следующих n строках задано описание поля — по n символов '.' или '#' в каждой строке.

В следующей строке задано одно целое число q — количество выстрелов.

В следующих q строках заданы выстрелы. Каждый выстрел описывается двумя целыми числами r и c — номером строки и номером столбца клетки.

Выходные данные

Для каждого выстрела выведите в отдельной строке одно из слов:

• miss
• hit
• sunk

Ограничения

• 1 <= n <= 1000
• 1 <= q <= 10^5
• 1 <= r, c <= n

Гарантируется, что исходная расстановка кораблей корректна.

Примеры

Пример 1

Входные данные

1
#
3
1 1
1 1
1 1

Выходные данные

sunk
miss
miss

Пример 2

Входные данные

3
#..
...
..#
5
2 2
1 1
1 1
3 3
2 3

Выходные данные

miss
sunk
miss
sunk
miss