Dwarf the Puzzler 正在为其他矮人设计迷宫谜题。迷宫是一个 $N \times N$ 的正方形，每个格子要么是通道，要么是墙。其中一个通道内放置着一个棋子，它面向右、上、左或下四个方向之一。在每一步中，矮人首先旋转棋子，然后将其向旋转后的方向移动。当然，棋子不能移动到墙上或穿过墙！如果棋子移出了迷宫，则谜题解决。

矮人们很喜欢这些谜题，但 Puzzler 的老对手 Dwarf the Riddler 吹嘘说这些迷宫很无聊，他可以用一个简单的策略解决它们：在棋子当前面向的右、前、左、后四个方向的格子中，选择第一个是通道的格子，然后将棋子旋转到该方向并向该方向移动。Puzzler 对此并不信服，作为一名工程师，他想对此进行一些测试。请帮助他，针对他设计的迷宫以及棋子的起始位置（和方向），计算棋子最终是否会离开迷宫，以及需要多少步。

输入格式

第一行包含两个整数 $N$ 和 $Q$，分别表示迷宫的大小和询问次数。

接下来的 $N$ 行描述了迷宫，每行描述迷宫的一行，从最顶行开始。每行包含 $N$ 个字符，要么是点 .，要么是井号 #，分别代表通道和墙。迷宫的行和列从 1 到 $N$ 编号，从上到下，从左到右。

接下来的 $Q$ 行包含后续询问的描述。每个询问由两个整数 $r, c$ 和一个字符 $d$ 组成。数字 $r$ 和 $c$ 表示棋子初始所在的行和列，字符 $d$ 表示棋子面向的方向，其中字母 U、D、L 和 R 分别表示棋子初始面向向上、向下、向左或向右。

你可以假设棋子永远不会位于有墙的格子里。

数据范围

$1 \le N \le 1\,000, 1 \le Q \le 100\,000, 1 \le r, c \le N, d \in \{U, D, L, R\}$。

输出格式

对于每个询问，输出一行，包含一个整数：棋子离开迷宫所需的步数。如果棋子永远不会离开迷宫，则输出 $-1$。

样例

样例输入 1

10 10
##########
#.#.#.#...
#.....#.##
####.##..#
#....#####
#..#.#...#
#.#..#.#.#
#.#.##.#.#
#.#......#
###.######
2 10 U
2 10 L
4 8 U
10 4 U
8 7 U
8 9 U
6 2 U
5 2 U
3 5 D
7 4 R

样例输出 1

1
11
7
61
-1
54
11
-1
33
4