5597 - NOIP CSP 2024 普及: 第二题 地图探险

小 A 打算前往一片丛林去探险。丛林的地理环境十分复杂,为了防止迷路,他先派遣了一个机器人前去探路。

丛林的地图可以用一个 nm 列的字符表来表示。我们将第 i 行第 j 列的位置的坐标记作 (i, j)(1 \leq i \leq n, 1 \leq j \leq m)。如果这个位置的字符为 \tt x,即代表这个位置上有障碍,不可通过。反之,若这个位置的字符为 \tt.,即代表这个位置是一片空地,可以通过。

这个机器人的状态由位置和朝向两部分组成。其中位置由坐标 (x, y)(1 \leq x \leq n, 1 \leq y \leq m) 刻画,它表示机器人处在地图上第 x 行第 y 列的位置。而朝向用一个 0 \sim 3 的 整数 d 表示,其中 d = 0 代表向东,d = 1 代表向南,d = 2 代表向西,d = 3 代表向北。

初始时,机器人的位置为 (x_0, y_0),朝向为 d_0保证初始时机器人所在的位置为空地。接下来机器人将要进行 k 次操作。每一步,机器人将按照如下的模式操作:

  1. 假设机器人当前处在的位置为 (x, y),朝向为 d。则它的方向上的下一步的位置 (x^′, y^′) 定义如下:若 d = 0,则令 (x^′, y^′) = (x, y + 1),若 d = 1,则令 (x^′, y^′) = (x + 1, y),若 d = 2,则令 (x^′, y^′) = (x, y - 1),若 d = 3,则令 (x^′, y^′) = (x - 1, y)

  2. 接下来,机器人判断它下一步的位置是否在地图内,且是否为空地。具体地说,它判断 (x^′, y^′) 是否满足 1 \leq x^′ \leq n, 1 \leq y^′ \leq m,且 (x^′, y^′) 位置上是空地。如果条件成立,则机器人会向前走一步。它新的位置变为 (x^′, y^′),且朝向不变。如果条件不成立,则它会执行“向右转”操作。也就是说,令 d^′ = (d + 1) \bmod 4(即 d + 1 除以 4 的余数),且它所处的位置保持不变,但朝向由 d 变为 d^′

小 A 想要知道,在机器人执行完 k 步操作之后,地图上所有被机器人经过的位置(包括起始位置)有几个。

输入

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 T,表示数据组数。

接下来包含 T 组数据,每组数据的格式如下:

第一行包含三个正整数 n, m, k。其中 n, m 表示地图的行数和列数,k 表示机器人执行操作的次数。

第二行包含两个正整数 x_0, y_0 和一个非负整数 d_0

接下来 n 行,每行包含一个长度为 m 的字符串。保证字符串中只包含 \tt{x}\tt{.} 两个字符。其中,第 x 行的字符串的第 y 个字符代表的位置为 (x, y)。这个位置是 \tt{x} 即代表它是障碍,否则代表它是空地。数据保证机器人初始时所在的位置为空地。

输出

对于每组数据:输出一行包含一个正整数,表示地图上所有被机器人经过的位置(包括起始位置)的个数。

样例

输入

2
1 5 4
1 1 2
....x
5 5 20
1 1 0
.....
.xxx.
.x.x.
..xx.
x....

输出

3
13

输入

5
1 2 1
1 2 2
..
1 2 1
1 2 2
..
1 1 1
1 1 0
.
1 2 1
1 2 0
x.
1 2 1
1 1 0
..

输出

2
2
1
1
2

输入

5
100 96 1
78 92 3
x...xxx..x........x.xx...x......xx.....x...x..x.x.xx..x.x.x...x...x...x..x..x....x.......x.x...x
x.x...x.x....x.x.x....xxxx...x..xx.xx...........x.x...xx.....xx.x.x.x..x.xx....x.x.......x..x...
..x.x..xx.xx...x..xx..x..x.xxx.....x.....x.x.....x.x....x.x...x.x.x.x.x......xx.x.x...xx.....x..
x.x.xx..x...x....x.....x.x...x...x..x....x.............x.x....xx.....x.............x......x..x..
..x.......x..x.....x......x.x..........xx.....x.x.xx...x....x...........x..x..x.....x..........x
x........x.............x.x.....xx..x.....x.xxx..x...x..x..........xx.....x.....x.x......x.x..x..
.x......x........x.....x....x..xx.x..x.x.x.....x...x.x....x.x....x...x.x....x..xx..x..x.x.x....x
....x....xx...x..x.x...x.......x..xx.xxx.x...................x..xx..x............x.....x......x.
..xx....x.......xxx.......x....x.x.x....x......x.xx...x..x....xx....x..x.......x.x.....x........
.x....x...x.......x...xx........xx...x.x.x...xx.x..x.......x.xx..xxx.x..xx..xx.x.....x..x.......
.x..xx.....x.x.xx..x........xx..x.x......xxxxx.....x...x......x...x..x.......x.x..xx.x...x..x..x
.xx...x....x..........x...x..x.......x.....xx..x.....x.x.x.x.x.............x...............x....
x..x.x.....x.x..xx.......x.x..xx.....x..xx.xx.x.x..x.xx.x....x..x....x.....x.x.x......x.........
..xx...xxx..x..x.x.x.........x......xx.x.x......x..........x..x.....x.x.x.x...x.x.xx..........xx
xx......x.xx...x...xxx..........x.....x........x.xx........x.x...............x...........x.x..x.
.............x....x.x.....x.x....x....x..x.x....x..x.....x.....x......x..............xx.xxx...x.
..x..xx.............x.x.x..x.xx...xxx.x.......x..xxx.x.......x.....x.x.x.x.......x....xx...xx...
xx...........x....x..xx.x..x......x.x.......xx......x..xx...x.x..x..x.xx......x.x..x....x.....x.
x..xx.......x.x......xxx....x..x.......x.x....x.x......xx...xx.....x..x..x..........x..xx.......
....xx....x.x..x........x.........x...x..xx..xxx..x.x......................x..x......xx..x..x..x
xx.x....x.x......x.....x...xxx.x....x...xx.........xx..x.x..x...xx....x..x..xx.xx....x.xxx.xx...
.....x.......xxx......x...x.x.......xxxx.x.x.xx......x...............xx....x.....x......x...xx..
....xxx.x......xxx.x........x.x...xx.x...x...x..x.x......xx...xx......x.xx..xx....xx.x.x..x...xx
.....x.x.....xxx.....x.....x....x.......x..........x...........x..........xx........x.xx........
.x...xxx.........x..x.x.........x......x....xx.x....xxx.x............xx............x..x...xx....
..x.x.....x.....x............x........xxx......x..x..xxxxx...xx.xx........x...x...xx.x...x....x.
xx.....x....x..........x..x..x..xx.......x.......xx..x.x.x........xx.x...xx..............x....x.
.......x.....x..x.x....xxx.x..x..x......x.x...x...xx..x....x....x.xx..x......xx..x.x.......x....
........x.......x......xx....x..x.x.x.x.x.x.x.x.....x.........x..x....x.xx.............x........
x...x.......xx.....x......x.x.....x......x..x..................xx..x......x....x..x.x.x.x..x.x..
.....x.....x...x..x..x..x.........xx...x.....x.......x......xx.x.....x..x..x...x.x.x..xx.....xx.
.....xxx.....xxx..x.......x........x........x.......xx...........x.........x......x.x..x.....x..
...x...x....x..x.x.x........xx.x..x..........xxx..x.x.......x........xx.....x.....x....x..x.x..x
..x..x.x......xxxx..x.x..x.....x.....x.x.....xxx..xx.x.x..x..x.xxx..........................x...
..x...x....x......x...x.......xx.....x.....x....xx.x.....x....xxx.........x..x..x..x...xx.....x.
x......xx..........x.x.......xx.........x....x...x.x...x.x...x.xx..x........xxx...xxx....x.x....
.x......xx......................x........x..x.xx.x...x..x...x..x.......x.x....xxx.x....x.xx..x..
.x......x.x.x..x..x..x..x...x....xxxxx.........x.x.......xx.x........xx........x.x..xx.........x
...x..x.......xx....x..x..x.x.......xx..x..x......x.....xx..x.x.xx....xx...x....x...............
..x......x..x..x..x..x....x....x.x.x.x...xx...xxxx....x.x...x.....x..x....x...xx.x...xxx.....x..
...x.......xx....x.....xxx......x.........x..x.x...x.......x..x.......xx...x.x............x.....
....x...............x..x.xxx.x...x.........x.............xx.............xx.xx...x.......x...x..x
xx..x..x..x........x......x.x.....xx.x...x....xx..x...x................x......x.x...x..x........
........x...x.x....x....x.x...xxxx.x..x.....xx.x..x.xx........xx.x................x...x......x.x
.x......x....xx....x....x............xx.....x...x.xxx.x...x.x.....xx....x...............x...x...
...xxxxxx.x.x..x...........x..xx.x.xx..x..................x...x..............x.......x......x.xx
..x.x....x.........x.......x...x...x..x.x............xx.xx..x.xx.....x............x.....x..x....
.x....x..xxxx..x.xx.xx.........x..x......x.........x.x..x.............xxx......x.....xx.x.x.xx..
.x......xx.xx.x........x.....xxx...xx.....xx..x..xx.x.xxxx...x...x..x...x......xx.......x..xx..x
.....x.x.....x....x....x...........x.x.xxx.x.........x.......x..x..x..x.xx.x...x.x..x.....xx....
.x.x.....x.x.x.x.x...x.x.x.x......x.xx....................x......xxx.x..x...x...x.....xx.x.xxx..
..x..........x..x..x.xx.....x.x...........x.xx...x...xxxx..x.x...x..x.......x........x.xx......x
..x....x...x.....x.x......xx..xx.x..x....xxx........x...x.xxx....x..x...x...........x.x....xxxx.
.x.x..x..............x.xxxx.x...x......x...x.x.x...xxx......x....xx...........xxx.....x..xx..x..
........................x............x..xx.......x..xxxx..x.....x..x.xx......x.....x.....xx.....
..x..xx...x......xx......xx.........x.............x.................x.........xx....x.x.xx..x...
..x..x.x.x.......x...x....xx......x.xx....xx.x.....xx......x.xxxx....x.x......x...x....x.x.xxx..
.....xx..x...xx.x....x...xx..xxx.x.x...............x.....x..xx.xx.x..x...x...x.......x.x........
.....x.......x..x.....x.......x...xx....x.x..xx..x....x.......x............xxx.x..x............x
.xx...x.x..x..x...x..x......x.............xx.x.xx.x..x.....xx...x......x........x......xxx......
..x..........x....x....x..x.xxx....xx....x...x..xx...x..x......x.......x......x.....x.x...x.....
.xx........x.....x..x......x....x...x..x.....x......x..x.......x..x.xxx.x....x...........x......
x.x.x.......x..x.........x......x.xx...x....x.............x...x...x...........x...x...x.x...x...
...x..............x..x.......xxx......x...xx...x...x......xx..xxx.....x.......x..x.x..x.xxx.xx..
..x......x....x....x.......xx.........x.....x.x.xxxx......x..xx...x.......x.x.xxx..x............
x..x.........x.x..x..x...x..x....x......x.....x.x.....x..x....xx...........x.xx..x.......xx.....
x..x.x.x....xx....xx.xx.x....x.x.x.xx........x.x......x.xx......x..x..............x.xx.x...x.xx.
...x...x.x...x.xx..x..x...xx.................xx.............x...xxxxx.x.....x..xx...x.x.......x.
x...x.x..........x.........x.......x.x.x.........x....x.x..x..x.....x.........x............xx.xx
....x.x....x..........x.x..x.x....x......x..xx...x.x...x......x...x..x...x.xx.x.x...x...xx.xxx..
x.........xx..x..x......x............x..x...x..x....x..x...xx..xx...x......x..x........x..x..x..
..x.............x..x.xx..xx........xxx.....x.....x..x....x....xx........xx...x.......x......x...
.x.......x.....xx........x.x..................x...x.x..x......x.......xxx..................xxx.x
x...x......x.x.xxxx.xx..x..xx....xxx.xx.xx..........xx...x..x...x.x.....x...x..x.x..xxx......x..
......x.....x......xxx...xxxx.x..x..x...xxx..xx...x....xx........x.x..x.........x...x.xx........
x......x...x.....x....x....xxx.xx...xx..x..x...x.x..x..........xx....x...x.......x.xx...x..x.x..
.x.x........x....x.x.........x..x.........x..x.........xxxx.x.........x...x...x....x.......x..x.
...x..x........xx......x.xx.......x...x......x.xxx..x..x........x.x.x.....x..........xx...x.....
x.....x....x........x.....xx...x..x..xx...x....x..x.x....x....x.x.x.xxx.x.........x.....x.....x.
........x..xx....x......x....xx....xx............x...x.....x.x.....x...xx......x.xx.......x.....
.x....x........xx.xx..x.........x...xx......x.x....x......x..x.x........x.......x...x...........
...xxx......x...x..x.......x.......xxxx..x..x.xx.x....xxx.......x..xx.x.x..x.....xxx....x......x
..x.xxxx.......xx...xx...x.x...x..x.....xx.x...x....x.xx.....x..x...x.........x........x..x.....
x.x.xxxx..........x.......x.x...xx.x...xx....x.......x...xx..x....x.....xx.xxx....x..x.........x
......x.x..x...x......x..x....x.xxxx.....x...xx..x.xx.......x......xx....x.x.x.x..x..........x..
.x.....x....xxx...xx..xx..x............x....xx.x....x...............x.xx.x...x...xx.x...x...x.x.
xx..xx.x.xx....x......xx..x.....................xxx.xx..x.......x...........xx.........x.xx.....
...xx...x..x.xx..................x......x....x......xxxx..x.xx.xxx.x..xx....x.....x.......x....x
..xx..xx.........x..x..........xx.....x.x.....x.x.xx....x..x..x.....x.x.x.....xx...............x
x........x.x...xx....xxxx..x.......x.xxx.x.....x.............xx.....x..x.xx..xx.x..x.x..x.x.....
.x.......x..x....xx.x.xxx...x.x.........x....x.x..x.......xxx.....x.......x..............x...x..
...x....x..x.x...xx..x..........x.x.xx.....x..x..x........x..xxx..xx..xx..xx...xx.........x.x...
.....x..xx.x.x.x..xx..x.x.xxx..xx.x..x..........x..x.....xx.x..........x...x.....x.xxxxx.x.x....
......x.x......x......x..........xx....x.........x.x........................x..x.xxx..x....x....
x........xxxx.....x....x..............x..x...x....x.....x..x..xx.x.x...xx.........x..xx...xxx...
......x.........x.......x............x...xxx.xx.x..xx...xxx..........x.........x.xxx....x...x...
.x...x...x...........xx.......x.....x.........xx...xx.x..xx...xx...........x.x.x.....x..x....x.x
......x..xx..x.x..x.xx....x....x..x.xx..xxx.xx...x......x.......xx...x......x...x........x....xx
....x.......x.xxxx.x....x...xx.......xxx........xx..x.....xx......................x.xx.........x
.x..x...........x.........x..............x........x......x...xxx......x...xx.x....x...xxxxx.....
98 99 1
4 88 1
.x...x.....xx..x...xx..x.x.x...x.x.x.........xx.x..xx.............x.xx..x...........xx..x....x.....
..x..x...xxx.xx......xx.x.x..............x..x...........x...........x.....x.xx..x...x..x..xx.xxx...
.x......x..x.xx...xx...x.....xxx....xx.x..x............x..x..xx......x....x.x........xx.x..........
.x......xx.x..x.xx...xx..x..x.x....xx.x.x......x................x.xx....x........x..xxx.x....xx.xx.
..x....x.x.....x...x.x.......x.x......x.......x....x.....x..x...xxx.......x.xx....xx....x.x..xxx..x
....x.....xx....x.x.....xx.......x.....x.....x..x.........x....x..x...x...xxx..x.....xx.x.....x..x.
.xx..x...x....xx.xx..............x.xxx..x....x.x.x...x.x.xx.x..x..x..x..x.xxx..............x.......
x.....x.x...........x..xx...x......x..x..x....x..x..x..x....x..x..x...x....x........x....x....x...x
.xx...x..x..x..xx.....x.x..........x.......xx.....x..x..x........x....x..xx.x...........xx.....x..x
...x.xxxxx.....xxxx...xx...x..x......xx....x....x..x..xx.x......x......x......x....x........x......
..x.xx.......x..x....x.xx..xx...x....xx...x.......x.......x.....x.....x.x.xx..x..xxx.....x..xx.x.x.
....x..x..x.xxx........xx...x.x.........x..xx..........x.x...x.x...x.x...xx..xx.xx.......x....x....
.x..xx.x.x.........x........x..x..............x..xx.....x.....x..x..x.xxx....x....x....x.x.........
.....x.xx.....x..xx............x.........x.x...x....x......x.xx.....x.........x...x...xx.x.x.......
...x.xx........xx...x..xxx......xxx..x.......x..xx....x.x........xx...xxx....xx...x.xx...xx....xx..
.........x.xx.x......................x.x....x....xxx.xxxx..x...x.xxx...x..xx..xx.....x.x.....x.....
........x....x.....x..x.x.xx.......x...xxx......xx.x..x...x..x.x.x....x......x...x.......x.x.xx....
...x.......x.x......x..x..x.....x.......xx.....x.x.......x...x.x.......x..xx......xx....x.xx...x..x
.....xx.x.x...x.x.......xx..x..xx....x.....xx.x.........x..x...........x.....x.xxxx....x..x........
x.x...x.x...x.......xxx...x...x..xx........x.....xx...................x.x.....x.....x.....x...x....
...xxx...xx..x.xx.........xxx.......xx........x...x.x...x...x..x.x......x.....x......x........x....
...x.x.x..xx...............x...xxx...x..x.x......x..........x..xx........x.........x......x.x......
.x......x..........x....xx.xx..xx.xx.xx...x....x.x.xxxx.x...x....x.x...x...x.x...x....x.......x.x..
.x.xx..x...x..x......x....xx......x.............x.......x..x...x...x..x.....x..........x.........xx
...x..x....x.x.x..x.x...x....x.x....x.x......x..x......x.x.....x...........x........x...x.x......x.
...x..x................x.x..xx.x.x....xx......x.x.......x.....xx...x..x..xx.x...xx..xx....x.x..x...
x.......x.x.......x...x......x.x.........x.x..x.xx.x..x..x..x....xx.....xxxx....x..xx.......x.x....
........x..xx.xx.....x.x.....x.x.................x.....x........x..x.x..x.xxx.x......x...x.......x.
.x.....x.........x.........x.x.........x..x..........xxx.x...x....xx.......x..............x.xx.....
......x..x...xx.......x.............x............x.x..xxx........x......x.xx....x......x......x....
.x.x.x......x..x...x.......x..xx...xxx.x....x..x..x................xx....x.xx.........x..xxx.x..x..
.x...x..xxx.x..xx......x........x..x.xx....x..x.x...x..x...x..x.x.............xx.......x...x.x.....
x......x....x..x.x.x.x.......x.x.....x...x....x......xx..x....x...xxx..x.xxx.x..............xx.x..x
x....x.xx.x.x.......x.x.xx.x...........x....x....x.....x.xx...x..x...x..x..xxx...x...x....x..xxx...
.xx.x..xxx...x...........xxx........x...........xx....x.x.x...x...x....x........x.x......x..x..x...
......xxx....x..x.....xx......x..x....xx.xx...x...xx.....xxxxx.....xx....x.xx.x......xx.xx....xx...
.....xx.x....x...x..........x.......xx....x.........x.........x..x.......xx......x.x........x......
x..x.......x..xxx....xx..........xxx....x...x....x..x....x..xx...xx..x...x.x....x..x...x...........
...x........x..x.xx...x.xx..x.xx..x.........x.x..xx...x..........xx.x.....x....x....xxxxx.......x..
.....x..x..x....x.x.x..x..x.........x...xx.........x.......x..xx.x...x...xx..x.xxx....x......x.....
xxx...xx...x.....x..x..........x........x..x...xx.x..x..x............xx.....x.......x.x...xx.x...xx
..xx.x..x...xx.xx...x.......x.........x...........x..x...x.x..xx...x...x..x........x..........x....
xxx..........xx.............x..xxx.xx..........x.....x.......x..x.....x...x......x...x......x...x..
.x...x.x.xx.x....x..........x.........x..........xx..xx.x.....xx.xx.........xx..x......x....x......
..x.x.....x..xx....x...x.x......x...xx..x.....x.....x....x..x.x...xx............x....x.x....x...xx.
.x..x.x.xxx..x..x..x.....x........xx..........x........x..xx.xx.......x.x..x..............x.....x..
.........x.....x....x.x.........x........x..xx....x..x.x..x..x......x..x........x......x.........x.
.x......xx.....x.x.x.....x.......x....xx.x.x........x...x..x.....x.x.........x..xxxxx..x..........x
xx...........x..xx.x...x.......x..x....xxx..xx......x.........xx.x..x.x.....xx.xx.xx.x....x.x..x...
x....x.x..xx...x......x.....xx...x........xx.x..x..x..x...........x.x...xxxxx..x.x......x.xx...x..x
........xx.xx...x..x.x.x.x....x..x..x...x....xxx..........x......................xx.x........x..x..
.....x..x.x..xxxx..x.x........x..xx...x.x...xx.x...x.xxx..x.......xxx...x........x.x.x.x..x.....x..
.x..x.........x.x.x...x..xx......x...x.........xx...x....xx...xx.x.x....x.x.x.....x...............x
...x...x.....x.x..x.x...xx.....xxxxx...x.x................x....xx................x....x..xx..x.x...
.x..x........x........x.............x....xxx...x.x..x...xx..xx.xxx.......x.....xxx..x..x.x..xx....x
...x.xx.....x.......xxx..........x..x.x....xxx.....x..x...x.xx...x...x........x....xx.......x....xx
.x.x.......x.....................xx..x.......x........x............x..x.....x.x.x....x.x....x.x....
.xx.xxx........x........x.x............x...x....x.x..x.x..xxx..x.......xx..x..x...x...x.........x..
...x......x......x.x.......x...........x.x.....x.x.........x.xx.xxx...x.x.......x.x.x..x..xxx...x..
x.....x.x....x..........x.....x.......xxxx..............x.x.......x.............xxx.x.xx.xx.....x..
.xx...x.x....xx...x.x...x..x......x.x....x....x...xxx..x.x....xx.x..x.x.x......xx.......xx.....x.x.
.x.......x.xx.......xx..xx........x....x....x....xxxx.....x..x..xxxx..xx.......x........x........x.
.......x..x........xx...x..xxx..xxx..x......x.x..xx..x.x.x.........xx..xxxx...x......x...........x.
....x..x...x.....xx...x.x.x.........x.x........x.x...xxx.x..x..x...x..xx.xx..x..x.......xx.xx....x.
x.x.....x.x....x....xx..x.x............xx.x...x............x.xx......x......xxxx.xx..x..x.....x....
.x....xx...x...xxx....xx....xx..x...xxxx..x...x.x................x........xx.................x.x.xx
x.xx.x.....x......x.....xx.....x.........x.x.....x..x..x...x....xx.........x...x..........x..x.....
x...x.........................x....x....xxx.xxxx.x.x..x.x.x....x.........x.x...xxxx........x.x.....
.x.xx..x....x.x........x....x.x.xx......xx....x.....x......xx..x......x.x......x......x......x.xx.x
x...x..x..xxx....xx....x....x.x.....................x.x.........xx..xxxx...xx......x..xxxx....x.x..
..x.x..xxx......xxx....x.....x..x....x......x......x..x.x..xx....x..x.x..x......x....x....x........
..x.x.......x..x..x..xx.........xx....x....x............x..x.x....xx..x....x.x.x..x...x...xxx..x...
x......x......x....x......x.x.x.x..x.x.........x.x...x.x...x.x.x..x..........xx....x....x.....x....
.x...x.x.....x..x..x..........x.......x....x...xx.....x...................x...........x.....xx.xx..
.........x........x.xx.xx....x.x..x.xxx.....x.........x..x.........x.x.xxxx..x..........x....x.....
.x.....x............x...xx...xxx.xx.......x....x......x.....x..........x......xx....x......x...xx..
xxx.x...x..xx...x.......x.x..x.x....x..........x.x.x..x.x...x............x.x...xx.xx......x.x.x....
....................x.x..x..x.x......xx...........x.....x.x....xx..xx....x.........xxxxx.xx..x..x.x
.....x.x.x.xx...x...........x..x...x..x........xx................x..x...x.xx.....xx.x..x.......xx..
.xx..x.x..x.......x...x...........x..x.xx.......x..x...x.x......x..x.x..........x.....x......x..x..
.x.......x..x.....x...x.x......x..xx.x..x.x.x....x..xx.x.xxxx.x...xx..............x.....xx...x.....
...........x.xx......x..x.x...x.....x.....x.x............x.x.x.xx...x.x.......xxx..x.x...x....xx..x
....x.....xx.x.x.....x.xxx...x..x....x...x..x......x..x.xx......x....xx.x.x..x...x...x......x....x.
x....x.x....xx..x.x...x.x.....x.......x....x.x........xxx....x.x..x..x.x....x.x.x..x......x.......x
.....x......x.x.x.........x.....xx.x....x......x.x.x....x..x...xx..........xx.....x..x...x.xxxxxx..
....x.x..x.......x......xx...x.x...x.....x..............x..............xxx..x.x..x....x.......x....
..xxx...x.....xx..x.....x......x...........xx..x.xxx........x..x...x......x.xx.......x.......xx....
.x.....xx............x.....xxx........x......x................x..x..x....xx.........x.xx.x.x.xxx...
.x...........x.....x.xx.....x...xx..xx.......xx.x....x.x.x....x.....x...x..x..xx........x..x.......
....x...........xx....x.x..x...xxx..x.....x.............x..x..x...x...x.......x...x.xx...xx..xx....
.xx..x.......x.x....x.......x..xx...x.x.x.x..x.x.......x.....xx......xx.xx.x...........x.......x...
x......x.....x......xx...x.x.x....x..x....x...x......xx........x......xx.x.x.xxx.........x...x..x.x
...x...x..x........xx....x....xx.........x...x..xx...........x......x....x.....x.....x.........xx..
.....x..x...x..xx....x.....x..x..x...x.x...xx....x.x...xx.x.......x.......xx..x.x......xx........x.
.................x...x.....xxx.....x....x......x.x.........x..x..xx....xx...x.x.....x..............
xx........x..x...xx...x....x.......x......x...xxx..x.x.x...x.xx........xx......x...x..xx.x..x.x..x.
.....xx..x...x..x.x.....xx............x.x.x..x.x.xx.....xx..x....x....x....x...xx...x....x...x...x.
x.xxx.x..x....xxxx..x.....x...x........xx...x.x.x.....x...x..x..........x..........x......xx....x..
99 96 1
92 48 0
..x..x.x...x..x...................xx..x..x.x.xx..x...xxx..x...x..x.x.........x.....x...........x
..x.......x.x..xx.x.x........x...x.....xxx.x.x......xx.............x......x..xx..xx.............
.x...x...x......x.x...x...x....xxx..x........x.....x....x.x.x........x.................x...x....
..x...x....x.........x.....x.x.....xx.x.x.xxx.....x...xx.x......x...x.x..x.......x.xxxx......x..
..x......x.x......x.x......xx.....x...x.x...x...........x....xx........x......x..xx.....x.......
.x.....xx......xx.xxx.x.....xxx.x..x..x...xx......x.x.xxxx.xx.....x..x...x...x.....xx..x..xxx.xx
x..x......x.......xx.x.....x.x....x.x.....x.x..x....xx..........x.xx.x.x...x.......x.x....xxx...
.x...xx.x..x......x.........x.........x.x.xxx.x.x.x.x........x..x..x.x....x.x....x.x....x.......
x....xx.x..x.............xx..x..xxx.xxxx.........xx....x......x..x.x.......xx.x...x.............
..x........................x..x..xx.......x...x......x........x.x.....x.x.....x.......x...x.....
..x..xx..x..x.x.xxx.....xx.x.x.xx.x....x..x..x..x.xxx......x...xx.........xx....x..x.xx.....x...
..x.xxxxxxxxx...x...x.x..x....xx..x...................x..........xx...x...x...x......x....xxx...
xxxx..xx.....x..xx.x.....x..x..x..x......x.....x.x.........xx..x.x..x..x..x........x.x.....x....
xx...x.x...x.....xx.xx..x.........x....x.xx.xx...x.x........x..xx....x......x.x....xx...xx......
...xx....xx..................x......xxx..............x........x.x....xx...x....x.x..............
x.........x...xx.x......x..x.x........xx.xxx.x.xx..........xxxx..x.x...x..x......xx..x.....xx.xx
..xx......x..x.x......xx.xx.x......xx.xx............x......x...xxx.x..x.....xx.x...xx.x..x......
..x..x.....x........x...........x.x...x.xx......x.xxx..x......xxx..x.....x.x....x...x......x.xx.
........x......x...x..........x..........x.xx.....x.x.x.x.x.x...x..xx..x.....x......x.x.....x...
.x.....x.x..x......x.........x..x..x...x.x.x...x..x...x..............x..........x..xx....x....x.
x.......xx..x..xx.x......x.....x..........x........xx...x....x..x.x.....x....xx....x...xx..x....
x.x.xx.x.x...xx.xx.x.....x...x.......x.xx....x....xx.x.x..xx.xx..x.xx...x.x...x........x........
x...x....x...xx.x.x...x...x.....x......x....x.x..xx...x....xxx....x......xx......x....x..x......
x..........x...x...x...........x...x.xx..x......x.....x..x..x.x..x.....x...........xx.....x.....
....x.x......xxx.....x..x.x..x...x.......xxx...........x...x...........xx..x....x.x..x.....x.xx.
...x..x..x.....x.x..x..........x.......x...x....xx.......x..............x.......x............x..
..x.x........x...x.......xx...x..x.x..xx...xx..x........xx...x....xx.....x......x.........x...x.
x...x...x........x.........x.xx.x.x....x....xx..........x.x....x.x.........x....x..x...x.x......
.....x.x..........x.x......x........x.......xx......x......x........xxxxx......x....x..........x
......x...x.x..x......x..........x............x....x........x...x.......x..x.x...x....x.x.x..xx.
....xx....x.x..............xx.xx.x..xxx......xx.x...xxx.xx...x..x...xx.x.x.x...xx...x.....x....x
.x.xx...x...xxx.......x......x.....xx........x....x....x..x....xx.x........xx..x....xxx...x.....
.x..x.x....x.x...x.xx....x.x...x.x.......x....x..xxx..x..x...x...x........x..........x.x...x.x..
xx.......x....x...x....xx.........x........x.x.xx...........xx.xx..x....xx.xxx..x......x.....xxx
....x....x.xx.xx....xx....xxxx.....x.......x......x...xxx...x.x.xxx...x..x.x.......x...x....x.x.
....x...x....xx.....xx.x.xx.......xxx......x...........x....x....x..x..xx....x..x..x..x.x...x.xx
...x.xxx....x....x.....xx....xx..............xx....x.x.x.x.x.......x.......x................x...
.......xx.........x.xxx..x..xx...x..........x.x....xx.........x....x..x...x...x...x.............
..xx..........xxx.x.x..xx...xx.x.x..xxx.............x.....xx....x.......x...x..x..x.............
....x.............xx.xx.x.x..................x.................xxxxx.........x.........xxx......
.......x............x...x...x...x.x.x..x...x...x....x.xxx.......x......x..........x..........x..
xxx.x.........x......x....................xx......xx...xx..x..x.x..x..x.x....x.........x.x.x..x.
....x..xx.x....xxx..........x....x..x...xx......x.........x.x........x..x.......x..xx...x.......
....x....x.......xx..xx........x...x.x......x...x.xx.xx.x......xxx...x.xx.....x...xx..x..x.x.xxx
..x...xx..x....x..x....x..x..x.........x.x..x.................xx......x.x...x.x.x.xxx.......xx.x
......x....xxx.....x.......x.......x.x.x....x........x......xx.....x..x...x.xxx....x.....x....x.
.....x.x..x......x.......x.....x.........xx..x.......x...x.x..x..........xxx.xxx..........x.....
......x.xxx.xx........x.........x....x....x..x...x.......x.....x...x......xxxx.........x........
x.xxxx.xx..x..xx.xxx......x...x.x..x..x.xxx.x..xx...x.x.......x.x.......x.....xx..x...xxxx..x..x
..x....x.......x.....x..x.x.xxx....x....x...x..x.....xx...........xx....x...x..xxxxx....x....x..
....xx......x.......x..xxx..x.xx....x..x...............x..x..x...x.....xx....xxx.x.........x...x
......x.....x......x.x....xxxxx.x.........x...x...x.x....x...x...x..x.x........xx.....x.........
......x........x....x...x...xx..x.xx..x...x.xx.x....x..........x...x..x.......xx..x.x...x...x...
.x.xxx......x..............xx.....x..........x...xx..xx.....x.....x..xxx..x.......x...x.........
...xx.xx..........x....x......x..x............x...x.x.x.x..x.x....x..x...x....xxx...............
......xx..x......x.........x..xx...x..x.xx........x..x..x..x...xxx....x.....x.xx.xx.x...x...x.x.
..x.......xx.xx..xx..x...x.x.........xx.......x.....xxx......x.x.x....xx......x.........xx..xxx.
xx..xx..x......x.........x.xx....x..x..x....x.x...x.......x.xx.x...x.xxx.xx.....x.x...x.x...x...
.x.xx..xx.....x.x...................x.......x..x...x.xx......xxx.........x.x...x.........x...x..
xxx...x...x..........x...x..x..x....xx..x.xxx..x......x.........x...x.xx.....x....x........x....
...x.........xx..x..x.....x....x.....x...x...xx..x.x..x....x......x........xx..x...........x...x
..........x.x.....x...x..xx.x....x...x....x...x....x...x.....x.....x.xx.x.xx.x.xx.x....x..x.....
.xx...x.xx.......x.....xx..x.xxx....x...x.......x.xxx.....x.x......x...x......xx.......x.....xx.
....x...x.x.....x.x..xx.x...............xx...x.x...xx.x..x.....x.......x.x...xx......xx...x.....
..xx..x.x.x..........xxx...............x....x.xx..xx...x...x...............x...x...xxx.......x.x
.....x......x...x.xx........xxx...x..........x.......x....x.xx....x...x...x.x..x...x.....xxx....
x.x....x.....x.x..............xxx..x...x......x.....xxx.....x....x.x.....xx.x....xx....x..x....x
......x.x....x....x...xxxx.x.x....xxxx..xx.....x..xxxx............xx.x.x.....x....x....xx...xx..
x...xx..x.x.....x.x.x.x...xx.......xxx........x.xxx.x.x..x..xx........x...........x.x.x...x.....
..x........xx.......x.x............x....x..x.xx..x.xx...xxxx.......x....x...x.....x...x.x.......
..x........x...x......x.x...x.....x.......xx..x..x..x.........x..x......x..x......xx..x..x....x.
x.......xx..x....x...xx.x..xx.....x.x.x.x..x.................x..x.x...x........x........x..x.x..
.x.x..x...xx..x...xx.x........xx.x..x.x...x...x...xx.x.x.....x..x....xx...x....x.x..x.x.......x.
.x.xx........x..x..xx.........xx.....x..x...x...x.....x.....x..........x..........xx.x.x.x....x.
.x...x...x.x.....x..x.......xx........x.x....x.x.x...xxxx...x....xxx....x..x....x....x..x.x....x
x..x..x.x.....xxxx.x....x....x..........x...x....x.x.....x....x.x..xxxx...x.....x...x..x.xx...xx
xx.......x.....x.......x...........x...x.xx.......x.x..x..x......x.x...........xxxx...x......x..
...x....xxx.x....x.....x....xxx.........x.x..x...x..xx.............x............xx...x..........
.........xx......x.x..........xx.x.....x..x...x.......x..........x....xx.x.x....x..x...xx....x..
...x......xx..x.....x..x........xx...x...xx.xx..............x..............x...x.......xxxxxx...
..x.....x.....x.......x...x........x..x....xx.xxx.....x.x.....x.......x....xx.xx....xx.......xx.
...........x..x.........x......x.x.xx...x.......x....x.x....x.....x...x...x........x....x......x
.........xx.x...x..x............x.x...x.xxx....xxx.....xx.......x...xxxx..x.x..x.....x.x....x...
.x.xxxx..x.x........x.......x.....x...............x........x......x...xx..x.........xx.....x....
xx..xxxx......x....xx....xx.........x...x.....x...x........x.........x......x..x....x..x...x....
.....x...x.xx..x...xxx.xxx.....x...x...........x..x...x.xx...xx...xx..x..............xx..x......
x.......xxx.x.......x......x..................xx...x.........x...........x.x.....xx...x..x......
.....x....x....x.....x.x.x.....x....x.............xxx.x..xxx...x...x.........xx.....x......x....
....x.xxx.........x.....x..x..x.......x.......x.x...x...x.x.................x...x...x.x.xx......
..xxxxx....x..x..x..x.....x....x..........xx...xx..x..x.........x...xxxx.x...x..x.x....x.x......
....x.x..........x..............x....x................xx.xx.x.....x......x............x...x.x...
x.x...x.....x..x....xxx...x..........x.x.xxxx......x..xx...x.xx......x...xxx.................xx.
.....xx....x.x..xxxx....x..xx.....xx...........x................xx..x..x.....x.x....x........x..
......x.x..x....x.....xx....xx.x...............x.x....x............x.xxx...x.......x.x....x.....
...x......................x.x.x.....x.......x..............x..x....x...........x.x........x..x..
.........x............x..x..xx............x...........xx......x...x..x...xx...........x.x..x...x
....x..x...x..x.x....x.x......x.............x..x....x......x....................x.x..x..x.....x.
........x......x.....x..x.x....x.x....xx....x....x.......x....x......x..x....x.....xxx.x.x..x...
..x.xxxx.x..x.xx.xx..x...x...x.x....x.xx..x....x.x.x.....x.x..xxx.....x..xxx...............x...x
98 99 1
3 11 1
xx...x.....x.xx.....xx..x.x..........x.....x.......x.x.....x...x....xx.x...x......x..x.x..xxx.x.x..
.x...x...........xxxx.xx..x..xx.xx.....xx...x.....x....x.....x.......xx...xxx..x..x..x..x.x.......x
x....x........xx....x.xxx............x..x.xx........x.....xx....x....x.xx.x.........xx..........x..
..x.......x..x...x..x.x..x....x.x.x.....xx...xx.x....x........x...x..xx....x..x.x.....x...........x
.xx............x.xxx..xx.....x..x....x.........x.........xx..x.xxxx...x......x..x....x...xx...x....
.xxx..............x..x..x..x......x..x....x....x....x..x..x....xx....x........xxx.....x.x..x.......
............x...x..x...xx.xxx.........x.....x..xx.x...xx.x......x..x.........x...x....x...xxx.x....
..x.xx.......xxx.x..............xxx.....x.x.xxxx..xx.....x........x..xx...xxx..x.xxx.............x.
......xx......x.x...xx...x....x.x.x....xx......x.xx......x.....x.x...x...x.....x.....x...x.........
.......xxx.........x.....x..........xxxx.x....xx....x.x..x..x................xxx....x...xx.........
x......xx..............x.xx......x.................x........x...............x..xxx...xx..x.x.xxxx..
....x............x..x...xx.xx..x..x.xxxx.xx...x...x..x..x..x....xx..x...x.x..x..x..xx.....x....x...
..x.....x...xxx..x.xx..x.x.x....x..x..........x....x...x......x.........x..x....xx.x....xx.xx......
....x..x....xx......x...x..x....x..x.x.x...x............x....x..x.....x............x.........xx....
...x........x..x......xx.....xx.x.x..x.............x...x.......x.......x.....................xx....
........x..x..x.x....xxx...xxx....x....x.............x...xx..x...x.x........x..x...x...xx...x..x...
......x...x...xx.........x..x.xxx.x...x.......x....x.....x..x.x..xx..x...x...x.x..xx.......x...x...
..x...x............x.x.x................x.x......x....xx.x...................x..x..xx.x.x..........
..xx.............x.....x.....x..x..........xxxx.......x....x.......xxxx...x......x.x....x.....x.x..
........x.x.x..x..x....x.x................x.xxx..........x.x.x.......x.........xx...x...x....x...x.
x.x......x.......x...x..x.....x........x...xx....x.x..x....x.x.x..x.x.x.......x.x..x............x..
.....x..........x....x...xx.xx...........xx.x..x...x...........x...xx.......x.....x....x..x.....xx.
..x...x.x....x.........x.....x..x.xx.......xxx......x.x..xx..x........xx..x.x.x..xx.....x..........
..x..x....xx..x...xx.x....x......x........xx....x......xx....x........x.x..x........x....xx........
.xx........xx..x.....x......x.....x.x.x..........x.xx....xx.....x.....x.x.......x..x.x.x...........
..x.x........xxx...x.....x.x............x.x....x..........x.....x.xx........x...xx.....x.........x.
..........x..xx..x....x.x....xxx.............x......x...x.xx....x.x....x............xx....x...x....
......x..xx.xx..x..x..xx..x...x.......xx..........x..xx...x.........x..x.x...x.x..x..........x...xx
..x.......x.x.....x.................xx...xxx..xx...x...x.xx......xx..x.x..x...x..x....x..........x.
...x....x......xxx........x....x......x..x..xx.x.xx.x..x...xx.xxx..xx...x.x....x......xxx........x.
..xx................x.......x..x.x......x...x.........xx.x.xx..x.......x.xx.x......x...x.x.x.x....x
.xxx.xx...x.xx......x..x......xx..x...x......x....x............x...x.........xxx....x....x..xx...x.
.....x........x...x.x..........x.xxx..............x..x.x..x......x...x........x.x.x...x....xx.x.x.x
..x......x...x.x..x.x....xx...x.xx...x.....x..x..x.xx........x..x....x.....x........xx.....x....x..
..x.x.....x.x.............x....x........x.....x..x...x..x.x..x.x.......x.x..x.....x...xx..xx...xx.x
.x...x....x...x...xx.......x...........x...x.....xxx.....x.....xx.x.......x...x.xx.x..x............
.....xxx...xx.x...x...x..x....x..........xx.x................xxx........x..x..x..x.xx...x....x..x.x
.....x....x.....x...x.........x.x......x.xx.xx......x.xx.x.....xx............x......x....x.....x..x
xxx..x...x..xx........x.x....xx.........xxx.xx.x..x....x.......x.x...x..xxx..........x.......x.x...
.....x..xxx.....x.....x.x....x...x......x.xx..x..x.....xx.x..........x....x.............x..x..xx...
x....x.xx..x....x...........x.xx.........xxx...x..x...xx..xx....x..x.x..x......x.x......x..x.......
..xxxx...x...x...xx.xx.......x.x..x.xx.....x......xx...xx.....x.x.....x.............x.x...x...x....
......x...x.x......x.x..x.x..x.....x...x...x.x.....x...x....x.xx..................x.....xx...xx....
...........x.....x.............xx....x.x.......x.......x...........x.....x.x..x.x...x.x..xx....x.x.
..x....x........x.x...xxx.x.........x..x........x.x..x.xxx.....x...x...x...xxx...x............xx...
.....x.....x.......x....x.........x............x..x..........xx.x.x.......x.x..........x.....x.x.x.
x...x...............xx.......x..x.x.......x..x....xxx....x...xxx.......x.........x...........x.....
........x......x.......xx.x....x..x..x.x..x....x.xxx......x...x..xx........xx...x.......xx...x...x.
...xx....x......x...xxx...x..xx......x...x...x.xxx....x......xx...x.x.x..x..............x..........
xx.......xx.........x........x..........x........x..........x..xx..x..x.......x..x.x....x..........
..xx........x..x...x....x.....x.......x.x......x.............x..xx...x..............x..........x...
....xx...x...xx.........x.x....x................x....x.x......xx.x.x..xx........x....x.xxx........x
.....x........x........x.....xx...xx.x..x...............xx.x....xx.x..x.....x..xx....x..x...xx...x.
..x....x..xx..x..x...xx...x..x.x......x.....xx.x..x..........x..............x..xx...x......x....x..
.......x.x..x..x..x..xx....x......x......x....xx......x.x........x.......x...x......xx..xxx......x.
xx.................x.xx.x.x.......xx...xx......x..x.....xx...........x..x...x..x.xx......x.........
.x.....x.x.x.x..x....x....x.....x......x...............xxx...x....x.....x....x.........xx..........
...x.x........x.....x.....x......x........x...x..xx....x..xx...x..xxx.......x..x..x..........xx.x..
.....xxx....x....xx..x.....xx..xxx..x......xxx..xx...x....x..xx..x.......x............x.x.xx......x
x...x...x..x...x....x..........xxx.x.x......x.x..xxx.x.....x.x.....xx...x................x.x...x.x.
....x....x.xxxx..x.x...x..x.x.......................x..x.xx.....x.x...x..x......x.......xxxx..x...x
...xx.............x.x.....x...x....xx....xxx...x..x..xxx..xx....xxx...xx...x....x...xx.....x....xx.
............x.x..x.x..x..xx.xxx.............x.....xx...........xx.x.x..x...xx...xx...x...x......x..
.xx..x.x................x...x..........x.....x.xx.....x.x.x.....xx.xx.......x.......x...x....x.x...
..x........x...x..x.x.x...x.xx.x..x...xxx...x.....xx.x.x..x....x.xx.x....x.x..x.......xx........x..
....x..x..x...x.x.....xxx.......x.x......x....xxx.x..x...xxxx....x.x.......x.xx...x.....x..xx..xx..
....xx..........x.x.x....x....x......x......x....xxxx..x.x..x..........x.xxxx....x...x...x......x.x
x..x.x..x.x.............xx.......x....x.......x.....x...xxxxx.x..xxx...x...xx...........x.x..xx.x..
.........x....x..xxx.xx...x.xx.x......xxx.....x......x....x...x..xx..xx...x...........x.....xx.....
.x......x.xx.......x......xx.xx.x...x..x....x.......x..............xx.......xx..xx.x.x..x...x.x....
xx.x.x..........x...........x...x..xx.x..x........x..x..x..x............x.......xx....xx.....x..x.x
....xx....x..x.....x....xx...x.......x...........x.......................x..x........xx.......xxx..
....x......xxx.x..x.x...x............x.....xxx..x.xx...x.....x......x.x....x...x.......x.......x.x.
.....x.....x....x...x........xxx.xxxxx....x...........x.......x.x...........xx....x...x.......x....
..x.........x.......x..x..x...x.............x.x...xx..x..x...xx..xxx.x..........xxx..x.......x.....
..xxx..x.x.x.xxx.....x....x...x...x............x...x....x....x.....x........xxx.x.....x...x.x....xx
..x.xxx.x....x......xx........x.x...........x..x...xx.x..x.x....x....x..x..x.x.x.......x.x...x..x..
....xxxxx....xx...xx.x...........x..x.x.......xx...x......x..xxxxxxx.x..xx..x..x.x.xxx.x...x.......
........xxx......x.....x..........x....x.....x....x....x..x....x...x.x........x....xx..x.........x.
.......x..xxx...x.x...x...x.x...xxx....xxxx.....x.xx...xx...xx.xx.x.......x.....xx.x...x...x.x.....
.x..x.....x.........x............x........x...x......x..............x......xx.x....x....x.......x..
.xx..x.......x.x.xx....x.........x..xx............x......x..xx.x.x......x.x.x..xx....x......x....x.
.......x..x.xxx.....xx.x.x..x..xx.x..x.........xx..x..x......x.x..x...x..x.x...x....x.x......x...x.
....x.xx.......xxxx.x.......x...x..x....x.x......xx.....x.x..x..........xx..xxx....xx..xxx.xx.....x
x..xx......x.......x.x.x..x..x....x...x....xx.xxxx............x..............x...........x....x...x
...xx....x...x....xx..............x........x...xx.x....x.x........x.....x......x....x.....x........
.xx...xxx............x...x.....x..xx....x..xx.x.x....xx...x.......xxx...xx............x.x...x....x.
...x.x....xx...x............x.....x.......x.x.xx.......x......x.....x..x..x.x.....x..xx....xx....x.
x..x...x....xx.x.xx...x.x..x..x..x.x...........x..x.....x....x............x.....xx....x..x.........
..................x.....xx.....x......................x...x......x..xx..x.......xx.........x.x..x..
..x.....x....xxx..x...........xx..x..x.....xx..x.x.............x............x...x..x....x..x....x..
......x.x.xx.......xxx...........xxx........xx..x......x......x.x.x....x..x....x....x..x....x......
.......x..xx.x.xx......x..x.....................x........x..........x.....x.xxx.x.....x........x.x.
xx..xx...........x..............x....xx..xx..xxx.xx..x....xxx...........x.xx.x......xx.xx....xxxx..
....x.xx....x........x.x..x........xxx....xx....x.....x..........x.xx..x....x..xx.......x.x....xx..
.......x.x.x.xx.x..xx......x............x..x......x.............x....x.xx...x.x.xxx..xx........x...
........x....x...........x.xx....xxxx..............xxx...x.xx...x.xx....x.................xxx.x...x
..xx.............x.x..x...x.......x...x.x............x.x.x...x.x..x.x..x.......x.x........x.x......
96 100 1
3 65 0
......x.x....x.x..xx.......x....x.x.......x.x..x..x..x.xx..x....x...x.xx..xx..x.........x.x...x....x
.x...x..xx.xx....xx............x....x...........x......x.x.xx....xxx..x...xx.............xx.x..x.xx.
x....xx......x...x.xxx..x...x..x....xx.xxx.........x..x.......x..x........x.........x.x....x..x...xx
....xx.......x............x..x...x...x....x..x......x.x............x.x.x............x...x...x.....x.
.xx.x.x.......x.x..x..x...x...x.....x.xxx...x....xx.........x..x....xxx..xx...x..x.x................
...xxx......x..x...x..........xx........x.....x...x....x...x..x.x.......x.........xxx...x...........
x..x.................xx........x...x....x......xx.......x..x.x...xxx..........x.xxx....x.xx..x.x..x.
xxx......x......x...x.x........xxx..............x......xx....x.x..xx.........x..x.x..x........x.....
.......x.......xx..x....x.....x.....x.x..x.........................x......x....x..x.x...x.........x.
..x..xx.............xxx....x........xx..xxxxx......x.....x.....x.x.x............x.x..x..x..x........
.....x..x.x.....x.x.xx.x..x.......x.x....xx..........x..........x........x....xxxx..x..........x.xx.
x..x....x......x.x.x....x..x.x.......x..x.....x.x..x....x.xx.....x......x..x...........x..x.........
..x.x...x.xx...x..x....x.x...x..........x.xx......x.....x..x..........xxx...xx.x...xx.xx...xx...x...
.x.........xx.x..xx.x.xx..x......x.x.....xxx....................x....x.......x.x..xxxx.......x.x....
xx...xx...x..x..x.........x..x.x.x...xxx.....xx..xx....x............xx....xx.x....x...x.x.......x...
...xx...........x....x.xxx....x...x..x..x.x..........x.x....x..xx.xx..x..xx..xx...........xx.x.x....
x...................x....x.xxx.x...xxxx.x..x...x...x...x.....xxxxxx.....xx........x....xxx.xx...x...
x...x..x....x.......x..x.....x........x.........x...........xx.x..........xx..xx..xx...x......x..xx.
.x......x......x.x.......x.x....xxx....xx.x..........x..x.....xxxx.xx................xxx.x.x........
x.x....x..x..x..xxxx.....xx....x..x..xx.x......x........x.xx...x.x.x..x.....x.x..x..x.xx..x....xx..x
..x...x...x.......xxx......x.x..............x..........x.x.x......x.x....x.x...x.x..x.x.x.....x.x...
xx..xx....x...x.x.x...........xx..x............x...x.............x....x...x.......xxxx.........x...x
x.x.xx....xx.....xx.....x.x.x..........x.....x.xx.......x...x.x.......xx..x................x.....x..
...x....x.x..x.........x.....xxx......xx.xx..x..x...............x....x..x....xx.....xx...x..x..x.xxx
x...x..x.x...............x.............xxx...x..x...x.x........................x.x..x...xxx....x.x..
...xx...x.x.x...x....................x.....x..x......x..xxx.xx....x..x..x.xx.x........x....xx.......
x...x.x.x.................x...xx......x..x.x..x..x.x......xxxxx..........xx.xxx.x....x..xx...x.xx...
.x..x.x..x....x.xx..x........xx...................x.....x.x...x.x....x....x....x........x.x.........
x..xx........x.x.......x.....x.xx.x.x..x..x.xx..x...x.....x..x.x.xxx.x..x.xx.....x........x.....x...
.....x.x..x...x.x..xxx.x.x....x..x..x..x.x...x.....x......xxxx.xxx.x.xx......xxx.....x.........x....
...x...........xx......x...x....x............xx.........x..x......x...x.x.x.x.x.x.xxx.x.x..xx.......
x..x..x.x..xxxx........x.....x.......xxxx..x...x..xx.x...xxxxxx....x............x........x........x.
x...x.x..xx..x.........x...xx...........x.xxx..x....x.x....x.xx.xx.........................x..xx.xx.
.x.x....x.xx..x.x.x.xx.......x.....x......x.xx.x...x....xx....x..xxx.xx...x..xx....x.x........x...x.
.x.x...x.x...x.xxx.xx......x..x...x.x...x...x..x...x............x...........x...xx.x..x...x.........
.......x.x....xx.x.x.....xx......x...x...x...xx............x.............x.....x.x.x.xx..x.........x
......x.....x......xxx....x...x.x..xx...xxx...x..x....x..x...x...x.xxxxx..xxx..x.xx....x...x.....x..
.x..xxx.....x....x...x..........x......x...........xxx....xxxx............x.........x.......x..x.x..
......x........xxxx....x............xxx....x...x..xx.xx..x...x...x...x.xx....x.......xx.......x...x.
.xx...xx......x.......x.x.x.....x.x..x...x..x..x....x......x........x.x.x......xx....x.....x...x....
..xx...x....x.x.....x........x....x.......xx....x.x.....x......x..........x...x..x..x..xxxx...x...x.
........x.....x..xx....xx....x..xx.x.x....x.......xx...x...x.x........xxx..xx.x..x...xx.x.......x...
...x...x.x.x..x...xx.xxx....xxx......x.....x...........x.x.x........x.x..x.xx.xx..x..x..xxx.....x.x.
........x......x......x.......xx................xxxx.....x......xx......x...x.x....x..........x.x...
.x......x.......x....x..xx.x.x....x....x..........x..x......x.......x....xxx.....x.xxxxx...x........
....xx..................x.x.........x......x.x..x...xxx...x..x.x..x..x.........x.....x............x.
xx.x.......x...x........x..x.x...x....x..x.x..x........x..........x..........x...x....x...x......x.x
.......xxx....xx..x......xx.xx...x..x...x.......x.x.......xx.....x.xx.....x.xx..x.x...x.x..x.....x..
....x....x.....xxx...x...x.....xx............x............xxx..xx..................x.xxx..x.x.......
..x....x.x....x..........x....xx.....x..x.......x.xx....x........xx...x..x.x........x.....xx..x..x..
x.......x.x..x........x...x...x..x.xx.x.......x..........x...xx.x.....x.........x....x.xxx..x.x.xx.x
.......x.x....x..x.......x.......xx....x.xx...x..x....x......x.x....x......x.x.........x....x....x..
.....x..........xx.x..xx.....x.......x.xxxx..x..xx.x.xx.xx.xx.x...x....xx.........x..........x..x...
....xxx...............xx..x..xxxx......x.....x...x....x.....x..x.....x..xx.....x.....xxxx.....x..xx.
..............x......xx....x........x.......x...xx..xx......xx........x.x....x....x..x.xx.x.........
x......xx....x.xx...xx..x..x.x......x....x..x...xxx..........x.x........x.x......x...x..x....x..x...
.xx....x....x.x...x....x..xxxx...xx.xx..x....x...xx.....x......x.x...x.x......x..x.x.......x...x..x.
........x...x.....x...xx.x.......x.....x..x.x..xxx...xxx...x...xxx..........xx..x..x..x.x.........xx
....xx.xx.....xx.x..........x.........x......x.x..xx......x.....xx...x..x.x..x.x..x......x..........
x......xx....xx....x...........x...xx.xx.x.x........x...xx...xxxx...x..x..xx....x......xxx.........x
...x.........x.......x.xx.x.x....x................x.x......x.......x...x...x..xx.x........xx........
x...xx.......xx.x.......xx..xx........x.x.x........x....x.xx...xx.......xx..x...................x..x
.....x.........xx....x..xx.x..x.x...xx.xxx.....xx.............x...x.......x.......xx.....x..x...x...
x..x....x..x.......x......xx..x.........x.xxxxx.....x..x...x.x...x.x.x..x.xxx..x.x.....xx.....x..x..
...xxxx.........xxx..xx..........x...x...x.....x.........x..x..xx...x..............x.........x......
...xx.....x....x.......x........x......x..x.......x...x...xx..xx....x.xx....x.....x.x....x.....x...x
.x.......xx.......x....x..xx...x..x.x....x.x.x...xx.....xx..........x..x....x.......xx.x............
xx.x....x....x...xx......xx...xx..........xx.x.x..x...x...xxx....xx.xx..........x.x..xx.........xx.x
.xx...x.....x.x.........x.x...xx..x............xx...xx........x...xxx...x.x.x....x.x....x..x...x..x.
x....x.....x.......xx.......x.x....x..x.............xxxxx.x..........x.xx.....xxx..x.....x.......x..
..x..xx....x.....x......xx..x....x.........xx..x..xxxxxx..xx.x......xx..x...xx..x..xxx..x........x..
..xx.xx.....x..xx.x...............x..xx.........x.......x..x...xx.x.x....x...x..x..........x.x......
.x.x.....x...xx.xxx....x......x...x.......x.x.x..x.....x.........x.x.x...xx...x..x......x.....x.x.x.
......x.x...xx.xx....xx.x...............xxxx........xx.....xxx..x.............xx...x..xx..x.xxxx..x.
........xx..x...x...xx....x....x..x.x.x......x.............x....x.x..x...xx.x...xx.x..x...x.........
..x....x.x.x...x.............x............x..x..x..xxx....x.x...x.x..............x...xxx..x...x..xx.
.x.x......xx..x....x......xxx..x..xx..x.x....x....x...x.x........xx..xx...x....x..x................x
x.x....xx......x...x.....x.x.....x.......x.....xx.......x....x....x...x.x.......x.x..x...x.x..x.x...
x.x.xx......x........xx.........x............x...x..x...x....x..xx..x...xx...x.......x...x..x.....xx
x.....xxx...........xxx......x.......x.x.....x.x..xx..xxxx.x.......x......xx..x.......x.....x..x....
x...x.x..x.x...xx.............xxx..........x...x.x...x.x..x..xxx..xxx.....x........xx...x..x....x...
x..x..x..xx....x.........xxx..xxx.xx.x.................x.....x......x.x....x.x....x.....x..x...x.x..
..x..........xxx.xx.x...x....x..........x.x.x.x........x..x..x.x....x.xx.x.....x..........x...x.....
..x.x..........xx.x.x...xx..xx.....xxx..xx..........x...x...xx......xx...x.x......xx......x......x..
xxx...........x..x..xx....x..............x.x..x.x.....x.xxxx.x...x..x.....x..x...x..xx..x.........xx
xx..x.......x..x...x..xxx......x....xx.......x...x....................xx.......x..x......x........x.
xx..x..x...x.x...x.....xx.x...x......x.x....xx.xx..xx.x...x.x.x.x.....x........xx.....x.x.........xx
.....xx..x........x.....x...x.x..x..x..x...........xx..xxx......x.x......x..xx...x.........x.x......
....xx..xxx...x..x.......x.x....x..x........xx....x....x..x....x......x..xx.x.x.x..xx.x....x.x...x..
...x..x............x....xx..........x....x..xx............x..x.....x..x.xx...x.....x....x..x..xx....
xxx.xxx....x.x.................xx....x.........x..xx....xx.x......x..x....x.x..x.....x...x.xx..x....
....x..x....x..............x....x.xx...x...x..x..........xx..x...x...xx.....xx...x.xx.............x.
.x...x.........x..xx.x......x..................x..x............x.......xx........x.....x.......x....
..x........x.x.....x......x..x.....x........xx.x.x.xx.x.....x..xxx..........x....x.....x.x.xxx..x.xx
.x..x...x....x....x...............xx............x....x...x.xx.........x....xxx....x.........x.x....x
..xx........x..xx...x.....x......x...x....x.x.x.x.....x...x.x.....x..x...x..xxxx...x.xxx.....xx....x

输出

1
2
2
1
1

提示

【样例 1 解释】

该样例包含两组数据。对第一组数据,机器人的状态以如下方式变化:

  1. 初始时,机器人位于位置 (1, 1),方向朝西(用数字 2 代表)。
  2. 第一步,机器人发现它下一步的位置 (1, 0) 不在地图内,因此,它会执行“向右转”操作。此时,它的位置仍然为 (1, 1),但方向朝北(用数字 3 代表)。
  3. 第二步,机器人发现它下一步的位置 (0, 1) 不在地图内,因此,它仍然会执行“向右转”操作。此时,它的位置仍然为 (1, 1),但方向朝东(用数字 0 代表)。
  4. 第三步,机器人发现它下一步的位置 (1, 2) 在地图内,且为空地。因此,它会向东走一步。此时,它的位置变为 (1, 2),方向仍然朝东。
  5. 第四步,机器人发现它下一步的位置 (1, 3) 在地图内,且为空地。因此,它会向东走一步。此时,它的位置变为 (1, 3),方向仍然朝东。

因此,四步之后,机器人经过的位置有三个,分别为 (1, 1),(1, 2),(1, 3)

对第二组数据,机器人依次执行的操作指令为:向东走到 (1, 2),向东走到 (1, 3),向东走到 (1, 4),向东走到 (1, 5),向右转,向南走到 (2, 5),向南走到 (3, 5),向南走到 (4, 5),向南走到 (5, 5),向右转,向西走到 (5, 4),向西走到 (5, 3),向西走到 (5, 2),向右转,向北走到 (4, 2),向右转,向右转,向南走到 (5, 2),向右转,向右转。

【样例 2】

见选手目录下的 explore/explore2.in 与 explore/explore2.ans。

该样例满足第 3\sim 4 个测试点的限制条件。

【样例 3】

见选手目录下的 explore/explore3.in 与 explore/explore3.ans。

该样例满足第 5 个测试点的限制条件。

【样例 4】

见选手目录下的 explore/explore4.in 与 explore/explore4.ans。

该样例满足第 6 个测试点的限制条件。

【样例 5】

见选手目录下的 explore/explore5.in 与 explore/explore5.ans。

该样例满足第 8 \sim 10 个测试点的限制条件。

【数据范围】

对于所有测试数据,保证:1 \leq T \leq 5, 1 \leq n, m \leq 10^31 \leq k \leq 10^61 \leq x_0 \leq n1 \leq y_0 \leq m0 \leq d_0 \leq 3,且机器人的起始位置为空地。

测试点编号nmk特殊性质
1=1\leq 2=1
2=1\leq 2=1
3\leq 10^2\leq 10^2=1
4\leq 10^2\leq 10^2=1
5=1\leq 10^3\leq 2\times 10^3地图上所有位置均为空地
6=1\leq 10^3\leq 2\times 10^3
7\leq 10^3\leq 10^3\leq 10^6地图上所有位置均为空地
8\leq 10^3\leq 10^3\leq 10^6
9\leq 10^3\leq 10^3\leq 10^6
10\leq 10^3\leq 10^3\leq 10^6
时间限制 1 秒
内存限制 52 MB
讨论 统计
上一题 下一题