{"problem":{"name":"[POI 2022/2023 R1] kol","description":{"content":"你在一个 $m \\times m$ 的棋盘上玩贪吃蛇游戏，已知原本蛇长度为 $1$，内容为 `0`，在 $(1,1)$ 处，棋盘上存在 $p$ 个“食物点”，当一条蛇吃了一个“食物点”时，它将会在其头部增加一个食物点对应数值的部分，下图可以更清楚的演示吃食物的过程（红色数字为蛇身）： ![](https://cdn.luogu.com.cn/upload/image_hosting/8t9pu2","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9804"},"statements":[{"statement_type":"Markdown","content":"你在一个 $m \\times m$ 的棋盘上玩贪吃蛇游戏，已知原本蛇长度为 $1$，内容为 `0`，在 $(1,1)$ 处，棋盘上存在 $p$ 个“食物点”，当一条蛇吃了一个“食物点”时，它将会在其头部增加一个食物点对应数值的部分，下图可以更清楚的演示吃食物的过程（红色数字为蛇身）：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/8t9pu2br.png)\n\n现在你进行了 $n$ 个操作，存在移动操作（上下左右）和查询操作（询问一个点是否被蛇覆盖），请编写一个程序求出它。\n\n## Input\n\n第一行三个整数 $m$，$p$，$n \\ (1 \\leq m \\leq 2000$，$1 \\leq p \\leq \\min(m^2 - 1, 10^6)$，$1 \\leq n \\leq 10^6)$。\n\n接下来 $p$ 行，每行三个整数 $w_i$，$k_i$，$c_i \\ (1 \\leq w_i,k_i \\leq m$，$0 \\leq c_i \\leq m^2-1)$，表示坐标 $(w_i,k_i)$ 的点是一个存在食物为 $c_i$ 的食物点。\n\n然后 $n$ 行，每行先是一个字符。\n\n- 如果该字符为 `Z`，则紧接着后面两个左边 $w_j',k_j'$，表示询问 $(w_j',k_j')$ 的地方是否存在蛇身，不存在输出 $-1$，存在输出对应的内容（数值）。\n\n- 否则，按照对应顺序移动：上（`G`）、下（`D`）、左（`L`）或右（`P`）。\n\n## Output\n\n对应字符为 `Z` 的，输出对应的输出。\n\n[samples]\n\n## Background\n\n题目译自 [POI2022~2023R1 kol](https://sio2.mimuw.edu.pl/c/oi30-1/p/kol/)。\n\n注意：原题时限为 32s，为避免卡评测，此题时限改为 3s。\n\n## Note\n\n子任务分配如下：\n\n| 子任务编号 | 特殊性质 | 分值 |\n| :----------: | :----------: | :----------: |\n| $1$ | $m \\leq 300$ 且 $p,n \\leq 2000$ | $20$ |\n| $2$ | $m \\leq 800$ 且 $p,n \\leq 50000$ | $20$ |\n| $3$ | $c_i=0$ | $20$ |\n| $4$ | 无附加限制 | $40$ |\n\n本题中，子任务 $0$ 为样例。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9804","tags":["模拟","POI（波兰）","2022","2023"],"sample_group":[["6 5 14\n1 3 1\n5 1 5\n2 3 2\n3 4 1\n3 5 3\nZ 1 1\nZ 1 2\nP\nP\nD\nD\nP\nZ 3 5\nP\nZ 3 5\nD\nZ 3 5\nL\nZ 3 5","0\n-1\n-1\n3\n1\n2"]],"created_at":"2026-03-03 11:09:25"}}