{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eThe poor princess, after being kidnapped by the demon king and rescued by the knights time and time again, now faces another life-threatening test. The demon king has sent a message saying that he will devour the princess at time T, because he believes the rumor that eating the princess\u0027s flesh will grant him eternal life. The elderly king is extremely anxious and has called upon brave warriors from all over the world to save the princess. However, the princess is already accustomed to this situation and firmly believes that the wise and brave knight LJ will definitely rescue her.\u003cbr\u003eAccording to the spy\u0027s report, the princess is trapped in a two-layer maze. The entrance to the maze is at S(0,0,0), the princess\u0027s location is represented by P, the space-time teleporter is represented by #, walls are represented by *, and the ground is represented by .. The knights will be transported to the corresponding position on the other layer as soon as they enter the space-time teleporter, but if the position they are transported to is a wall, they will be killed. The knights can only move forward, backward, left, and right on one layer, and each movement takes 1 unit of time. Movement between layers can only be done through the space-time teleporter and does not require any time.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of input contains C, indicating the number of test cases. Each test case is preceded by a line containing three integers N, M, and T. N, M represent the size of the maze N*M (1 \u0026lt;\u003d N,M \u0026lt;\u003d10). T is as mentioned above. The next N*M characters represent the layout of the first layer of the maze, followed by the next N*M characters representing the layout of the second layer of the maze."}},{"title":"Output","value":{"format":"HTML","content":"If the knights can find the princess within T units of time, output \"YES\"; otherwise, output \"NO\"."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n5 5 14\r\nS*#*.\r\n.#...\r\n.....\r\n****.\r\n...#.\r\n\r\n..*.P\r\n#.*..\r\n***..\r\n...*.\r\n*.#..\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}