自动驾驶系统

一家科技公司有一块试验地用于测试自动驾驶系统。试验地由$n\times m$个格子组成，从上到下依次编号为第$1$到$n$行，从左到右依次编号为第$1$到$m$列。试验车位于其中的某个格子上，每次自动驾驶系统可以控制汽车往上下左右移动一格。汽车不能走出边界，也不能碰到障碍格。

你需要编写自动驾驶系统中的导航部分。在测试的一开始，试验地里没有任何障碍。你的程序会依次收到$q$条信息，它们的格式是以下两种之一：

? x y，表示询问从第$1$行第$1$列的格子出发，到达第$x$行第$y$列的格子最少需要移动多少次。
* x y，表示第$x$行第$y$列的格子变成了障碍格。

第一行包含一个正整数$T(1\leq T\leq 5)$，表示测试数据的组数。

每组数据第一行包含三个正整数$n,m,q(1\leq n,m\leq 50,1\leq q\leq 100000)$，表示试验地的尺寸以及信息的数量。

接下来$m$行，每行描述一条信息。其中$1\leq x,y\leq n$，保证每个格子不会被重复变成障碍格多次，且$(1,1)$不会变成障碍格。

对于每个询问输出一行一个整数，即最少移动次数，若无法到达请输出$-1$。

1
3 4 5
? 2 2
* 1 2
? 2 2
* 2 1
? 2 2

2
2
-1

Claris

Championship