5597 - NOIP CSP 2024 普及: 第二题 地图探险
小 A 打算前往一片丛林去探险。丛林的地理环境十分复杂,为了防止迷路,他先派遣了一个机器人前去探路。
丛林的地图可以用一个 n 行 m 列的字符表来表示。我们将第 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 次操作。每一步,机器人将按照如下的模式操作:
假设机器人当前处在的位置为 (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)。
接下来,机器人判断它下一步的位置是否在地图内,且是否为空地。具体地说,它判断 (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),方向朝西(用数字 2 代表)。
- 第一步,机器人发现它下一步的位置 (1, 0) 不在地图内,因此,它会执行“向右转”操作。此时,它的位置仍然为 (1, 1),但方向朝北(用数字 3 代表)。
- 第二步,机器人发现它下一步的位置 (0, 1) 不在地图内,因此,它仍然会执行“向右转”操作。此时,它的位置仍然为 (1, 1),但方向朝东(用数字 0 代表)。
- 第三步,机器人发现它下一步的位置 (1, 2) 在地图内,且为空地。因此,它会向东走一步。此时,它的位置变为 (1, 2),方向仍然朝东。
- 第四步,机器人发现它下一步的位置 (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^3,1 \leq k \leq 10^6,1 \leq x_0 \leq n,1 \leq y_0 \leq m,0 \leq d_0 \leq 3,且机器人的起始位置为空地。
测试点编号 | n | m | k | 特殊性质 |
---|---|---|---|---|
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 | 无 |