AT_rco_contest_2017_final_b 日本橋大渋滞

给你一个有 $H$ 行 $W$ 列的网格地图（类似于围棋棋盘的格子，每个格子有一个坐标），其中有 $K$ 辆车。 最上面一行是第 $1$ 行，最左边一列是第一列，$r$ 行 $c$ 列的格子表示为 $(r,c)$。 每辆车有一个初始位置 $(A_i,B_i)$ 和一个目标位置 $(C_i,D_i)$。在每一个时刻 $t$ 可以让每辆车移动到相邻的格子里或者不动（被移动的车会在 $t+1$ 时刻完成移动）。 以下情况不能移动： - 在 $t$ 时刻时想要移动的格子有车； - 多辆车同时移动到同一个格子； - 移动到了规定的地图大小之外。 你最多能发出 $T$ 个指令。 你要书写程序使得得分最大。得分计算规则如下： 若最终位置为 $(r_i, c_i)$ $$P_D=20+\sum\limits_{i=1}^K(|r_i-C_i|+|c_i+D_i|)$$ $P_T=10+L \times 0.01$（$0 \leq L

输入的数都是整数。 输出共 $1+K$ 行。 第一行输入 $ H $、$ W $、$ K $、$ T $，分别表示图中的行数、地图列数、地图上车辆数量和能给车的指示次数的最大值。 接下来 $K$ 行，每行输入 $4$ 个目的格。

第一行输出需要的指令数量 $L$； 在下面 $L$ 行上，输出表示在时间 $t$ 发送给每辆车的指令的字符串。 指令字符串由 $K$ 个字母组成，每个字符串的第 $i$ 个字母表示在这个时刻第 $i$ 辆车的行动。 `R` 表示向右 `L` 表示向左 `U` 表示向上 `D` 表示向下 `-` 表示不动

### テストケースの生成について 各テストケースは次の手順で生成されます。 - 初期マスの候補となる$ K $個のマスを、$ H\ \times\ W $個のマスの中から、重複しないようにランダムに選ぶ。 - それらの初期マスの候補を、ランダムに $ K $ 台の車に割り当てる。 - 目的マスの候補となる$ K $個のマスを、$ H\ \times\ W $個のマスの中から、重複しないようにランダムに選ぶ。 - それらの目的マスの候補を、ランダムに $ K $ 台の車に割り当てる。 ### ジェネレータとテスター ジェネレータとテスターを次のリンクから提供しています。 [ジェネレータ・テスター](https://gist.github.com/tomerun/00a0efb3b1d738494791e05ebf18c3d5) ### ビジュアライザ 入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。 - このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。 - このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。 - このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。 ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。 [ビジュアライザ](https://gist.github.com/tomerun/8fc27d5cce6408032336fd316d817a7c) ### Sample Explanation 1 注意: この入力はテストケースとしての制約を満たしていません。 車1の初期マスを $ 1 $、車1の目的マスを $ X $、車2の初期マスを $ 2 $、車2の目的マスを $ Y $ としたマップを以下に図示します。 !\[\](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAPAAAADwCAYAAAA+VemSAAARS0lEQVR4Xu2dwWtVxxfHxz8gFinJRurCQCsJtQgFI7iwJGBdZFEEo4vSTRN0UV1FiK6bgELBbBQFQVxoAiUgQiskkEVB3Qq6sASh1I2hi+Af8H6c+/M933u59925M+/c86738yALzcw9M9/5fu6ZmXtfZk+j0Wg4PiiAApVUYA8AV3LcaDQKJAoAMEZAgQorAMAVHjyajgIAjAdQoMIKAHCFB4+mowAA4wEUqLACAFzhwaPpKADAeAAFKqwAAFd48Gg6CgAwHkCBCisAwBUePJqOAgCMB1CgwgoAcIUHj6ajAADjARSosAIAXOHBo+koAMB4AAUqrAAAV3jwaDoKADAeQIEKKwDAFR48mo4CAIwHUKDCCgBwhQePpqMAAOMBFKiwAgBc4cGj6SgAwHgABSqsAABXePBoOgoAMB5AgQorAMAVHjyajgJmAN+4cQP1UeCTUeDSpUsmfTEDeHR01KTDBEUBDQW2trY0Lpt7zdIBlsy7vLyc2zCNAgcPHkzOcnvz5s0ejetnXZO45ahtpXOzdxcvXnRlZ2JTgI8ePerkp6zP9vZ2AvDIyEipABO3nBG20Pn58+dOfuRTO4DL7vDjx48TgKenp0sFmLjlAGyhc/uMsmw/i6qmGbjsDlsMsIhMXADWUgCAtZRtuy4AlyCy0Y2SDFzi9jsgfbogWc10ABiA1ajihqUmbevCAAzAai4DYDVpAdhi2x1D6xvaaiprFZcMTAZWo4oblpq0ZGAysL65AFhfYzIwGVjNZQCsJi0ZmAysby4A1teYDEwGVnMZAKtJSwYmA+ubC4D1NSYDk4HVXAbAatKSgcnA+uYCYH2NycBkYDWXAbCatGRgMrC+uQBYX2MyMBlYzWUArCYtGZgMrG8uANbXmAxMBlZzGQCrSUsGJgPrmwuA9TUmA5OB1VwGwGrSkoHJwPrmAmB9jcnAZGA1lwGwmrRkYDKwvrkAWF9jMjAZWM1lAKwmLRmYDKxvLgDW17jWGfj77793p06d0lf5Q4TXr18nR6t89dVXpR6tQtxyhthC5z/++MP9+eefSQfLPmlEYpqezCAAy09Zn7///jsB+MsvvywVYOKWM8IWOgu8tQW47DsWU8pyQKqTzrWeQgOwLlB1AkmUtOgvALMLrUaxhaGtQLKKC8AADMB9UsDihgXAANwn++6+jIWhrTKhVVwABmAzgFdXV93Ozo47e/asGxoa8mrH+/fv3cOHD5OyWfXqdOMAYAD2AiekUC+Q7ty54+bm5pLLTk5OuvX1da8QFy5ccLdu3UrKLiwsuMXFxV31ANhLyr4UMn0OzC50X8Yw8yK9QLp+/bq7fPlyq+61a9fc/Px8zwa1Qy8Fz58/727evAnAy8uJBmX7WWICsC5DydUHMSPJVHh0dNRtb2+3FHj69KmbmJhIVeTVq1fuxIkTrfLDw8Nuc3PTjY2NATAAl0DRgIKk2fO8G8ezZ8/csWPHWk0QKLe2tlLXw1NTU25jY6NVdmVlxZ05cya1+XlxtfpsEZc1MGtgLT97ZX6faXH3dDtr7dvsiAVIVjMdAAZgU4AlePvGlPz79u3bbnZ2NmlXd5aWDa+1tbWeu9YArDakuy7MGrgErQfd0LIePn78uHvx4kWiRnN9+8UXX3Ssk3ute9tlHPT+9nPIycBk4H76qeNaRUCSTarx8fFWfcm0n3/+uZNnxc1Pr3UvALMLrWbkOq7NQtaE3evh9gHJW/cCMAADcJ8VKJKBm6G718Py/z7rXgAG4D7bd/flQgzdj0ZVKW7WejjteW+WNlXqb+z4sgZmDRzrocz6oSDNzMy01r7yrFfWvkU+oXGLxEgraxEXgAE41rcA/EEBAFaz0scLW96xLAY4ZDOpX8MQ2l8ysP8IWPpZWslzYP+xCi4ZClJwwMiMBMD+ygMwU2h/txQsGXrjAGB/oQEYgP3dUrBkKMBXrlxxS0tLSTQ2sXqLDsAAXBBL/+KhAMujpOZ3hX/55ZfUrwz2akVoXP+epZe0iAvAABzr277vQsc2yAIkq81CAAbgWF4AOHLTLmYAABiAY/zTs26dMiEZWM1GnRe2vGNh6HIGuU46W/pZRtP0OTCnE+oCZXFan/SoTnE5nZDTCdUotjitTzpTp7icTsgaWA3gOk1lWQOr2Yg1MCCVYy4LnWu9Bi77D2FbDLBVZiBuOTcNAGYKreY0blhq0rYuDMAArOYyAFaTFoBFAabQvQ3WfhLg119/nXnsSdZVABiA+66A5ZSjSoaWvxB59erVjrOI3r17V2g8qtTfQh3LKGzRX0s/m7/IQQbe7UT5+8znzp1r/ZH19hL//vuv279/v7fXLQxdt80zAGYN3AHkN998kwqvFOp1emAa1QDsfa8LLgjAANxhnpGRkY4jP9t/CcC9ObO4YQEwAHe48smTJ+7u3bvJmUT79u3rOIQbgAG4WwHTLzOwBu5tyO6jTgAYgAG40XDT09N7ghc9ARVDp3YAXEzsUJ2LRekszRSaKXSmfwC4GFoAXEyvoNKWdyyLAY55rALAxSxmMb6WfuY5cDF/BJcONRYAF5M8VOdiUZhCu+Xl5UQFNrHYxIqBp7suAPdTzYxrWU45LAaYKXQJpvoQwmJ8Lf3MFLokb4Uaiyl0sQEK1blYFKbQTKE9HQPAnkKRgYsJFVPacsphcYdmCh3jlmJ1LcbX0s9MoYv5I7h0qLHIwMUkD9W5WBSm0EyhPR3z7Nkzd+zYsVbpRqPhWfP/xSwMXbe4ZGDexOoJpRz1ubW15U6fPp0c9VnkA8BF1AorC8AAHOYcj1oA7CFSZBEABuBIC2VXB2A1aVsXBmAAVnMZAKtJC8CiAK9S6hoMgHX1lavXOgNzOqGuwep0SqAoadFfTifkdEI1iut0SqCIaNFfTidkDawGMFNoNWlZA7MG1jcXAOtrXOs1MJtYugYDYF19a7+JBcC6BgNgXX0B+OJFd4k1sJrLAFhNWtbArIH1zTXIAK+urrqdnR139uxZNzQ0lCuGT3mL/rIGJgPnmje0gIWhpa15cdu/Jjk5OenW1tZ6Qtxdfn19PVWSvLihOvaqB8AArOGr5JoWhvaJ2/095/Pnz7ubN2+m6iCZd2ZmpvW74eFhl3XMqkV/ARiAawewHFx+/PjxjlMYFxYW3OLiYocWctTqiRMnOg57W1lZyfxaJQCrWenjhS3vWBYD7JORtGQf5P7mwfn27Vt35MiRDnhv377tZmdnM+Wy6K+ln0UIDjfToqftuhbGqsKNQ05ilPfh2z9ygNv4+Lj74Ycf3MbGRutXaRm6e+gsdAZgptBqtxALQxe9cXSvh2WN+9133zlZ+zY/PhtdReP2S3QABuB+eWnXdaoAsDRa/mzQ0tJSqg4CtPxJIZ9HTRb9BWAArj3AIsDU1FTHlFn+T+Dd3Nx0Y2NjXhoBsJdMcYUs71gWA2w1tata3LT1sPwRP9l19v1YjK+ln9nE8nVGZDkLY1UJ4LQd6abkeTvP7UNjoTMAM4WOvD1kV7cwdNEbhzwT7t5x7u6RfGn+5MmTuTpZ9BeAATjXmKEFLAxdFGB5y6p7x3lubm7X21c+a2GL/gIwAIfymVvPwtBFAO7efT58+LD766+/kh3nXr/L6rhFfwEYgHNBDC1gYWhfgNPece7OsmnZOeuLDL5xQ7XMqgfAANxvT7WuN6gAd5/5JA2WN7AmJiY6tEhbH/d6I8uivwAMwLUDeGRkxPsLCmnvRGd9oQGA1az08cKWdyyLAbaa2g1qXMmqe/fubRnC5x1necwk70fnPVqyGF9LP4sefJmhhJuWhbEGFWBpl6x/f//9d/ftt9+6+fl5rxFo1hkdHXUCfdqrlRY6AzBTaC8DhxSyMPQg3zhCNMyrA8AAnOeR4N8DcLB03hUBGIC9zVK0IAAXVax4eQAG4OKu8awBwJ5CRRSrNcCcThjhHI+qFqf1SbPqFJfTCTmd0APFsCIWp/VJS+sUl9MJmUKH0elRiym0h0iRRWo9heZspEj35FQHYF195eoATAZWcxkAq0nbujAAA7CaywBYTVoAFgWYQusaDIB19WUKzfGiqg4DYFV5k4szhWYKreYyAFaTlik0U2h9cwGwvsZkYDKwmssAWE1aMjAZWN9cAKyvMRmYDKzmMgBWk5YMTAbWNxcA62tMBiYDq7kMgNWkJQOTgfXNBcD6GpOBycBqLgNgNWnJwGRgfXMBsL7GZGAysJrLAFhNWjIwGVjfXACsrzEZmAys5jIAVpOWDEwG1jcXAOtrTAYmA6u5DIDVpCUDk4H1zQXA+hqTgcnAai4DYDVpycBkYH1zAbC+xmRgMrCaywBYTVoyMBlY31wArK8xGZgMrOYyAFaTlgxMBtY3FwDra1zrDMzphLoGq9MpgaKkRX85nZDTCdUortMpgSKiRX85nZA1sBrATKHVpGUNzBpY31wArK9xrdfAnI2kazAA1tVXrg7ATKHVXAbAatIyhWYKrW8uANbXmAw84Bn4yZMn7p9//ulwwmeffeZOnTrlhoaGvBwCSF4yRRey0BmABxTgO3fuuKtXr7rt7e1MYy0sLDj5yQPZwljSaOJG3xNyLwDAAwbw+/fv3c8//+xWV1dzB08KTE5OurW1tZ4QA5KXlNGFLHQG4AEDeGpqym1sbHSY6fDhw+7QoUPJ//3333+7fi9ZeHFxMdOAFsYiA0ffD7wuAMADBLBMm+fm5loDNzw87B49euQmJiY6BvPt27fup59+aoEs5d69ewfAHxSo0w0LgAcI4CtXrrilpaXEhgLl5uamGxsbSwVTptgzMzOt3zUaDQAGYHepRD+L3HsavZznNYkoVsjyjpWXGV69euXk5RLZuHrw4EEmvNLjCxcuuFu3bgFwyvDn6VzMMf6lLeJa+hmA/b3RUbJ7qi0bWevr62RgMjAZOJApr2qxd2jZoZYpdnOa3Qz69OnTXevk9gbFxvXqXM0zodWmHRm4xDVDDEgyvT537px78eJFByorKyvuzJkzPRmLiRsKr5Wh6xYXgCsAcPeUubnJdf/+fXfy5MlcxgA4V6K+FLDQGYAHGOCslzpkzXvv3j23f/9+L+NZGKtumdCqvwA8oADLO9A//vhjx6uU8mjp119/dbOzs17gNgsBcCG5ggtb6AzAAwjw9evX3eXLlzuMJOvc3377zTvrsonVcNPT03uCaQyoCMABohWtYnnH8hngbnhDsy4AA3BRNkLK8yJHm2qy0zw+Pl5YR3lXuteLHz43jsJBPSoQ10OkyCKWCUmaDsBtA5i22+w7vjLFlkdKaR9A8lUxrpyFzgA8QGtg+ZLCkSNHen4HOMti165dc/Pz8wBcs+8hA/AAASz0yaOjly9fJiDu7Ozs+mscaYQeOHCg5/Ngi8wg7SRuXEb3qQ3AAwawz6AVLQNIRRULK2+hMwADcJhbPWpZGLpumR+AAdgDxbAiABymW5FatQb46NGjTn7K+mxvbydffx4ZGSn1BQPiljPCFjo/f/7cyY98yj6owPwxUjnD+jHKwYMHE4DfvHlTKsDELWekrXRu9q4WADc7Ozo6Ws6oEgUFSlBga2urhCi7Q5T+IkezCbJ24IMCn4oCZf8trKZuZgB/KgNHP1DAUgEAtlSf2CgQqQAARwpIdRSwVACALdUnNgpEKgDAkQJSHQUsFQBgS/WJjQKRCgBwpIBURwFLBQDYUn1io0CkAgAcKSDVUcBSAQC2VJ/YKBCpAABHCkh1FLBUAIAt1Sc2CkQqAMCRAlIdBSwVAGBL9YmNApEKAHCkgFRHAUsFANhSfWKjQKQCABwpINVRwFIBALZUn9goEKkAAEcKSHUUsFQAgC3VJzYKRCoAwJECUh0FLBUAYEv1iY0CkQoAcKSAVEcBSwUA2FJ9YqNApAIAHCkg1VHAUgEAtlSf2CgQqQAARwpIdRSwVACALdUnNgpEKvA/it96elfLix4AAAAASUVORK5CYII=) 全ての指示を実行後のマップは以下のようになります。車1は目的マスに到着しています。 !\[\](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAPAAAADwCAYAAAA+VemSAAAR6klEQVR4Xu2da6hU1RvG14Hom10ID1FZcY5ZKBV9CLWCCiUTEqJA60MXKiWjMgIN7UJXDYUoixLtQgSlRgkhZaDhN7Xoi5GFejpdITr0QYSICM6fd+fMf86cmdlr9p5nv7Pdv4Eh8qy91l7Pen77WWtfZg+Mj4+PBz4ogAKlVGAAgEs5buw0CiQKADBGQIESKwDAJR48dh0FABgPoECJFQDgEg8eu44CAIwHUKDECgBwiQePXUcBAMYDKFBiBQC4xIPHrqMAAOMBFCixAgBc4sFj11EAgPEACpRYAQAu8eCx6ygAwHgABUqsAACXePDYdRQAYDyAAiVWAIBLPHjsOgoAMB5AgRIrAMAlHjx2HQUAGA+gQIkVAOASDx67jgIAjAdQoMQKAHCJB49dRwEAxgMoUGIFALjEg8euowAA4wEUKLECAFziwWPXUcAN4FdeeQX1UeCkUWDFihUufXEDeHh42KXDNIoCCgVGRkYU1abWWTjAlrwbN25M3TFFgaGhoeRdbqOjowOK+tvVSbvFqO2lc613Dz/8cCg6iV0Bnj17drBvUZ+xsbEE4MHBwUIBpt1iRthD5wMHDgT72qdyABfd4Z07dyYAL1q0qFCAabcYgD10bpxRFu1nU9U1gYvusMcAm8i0C8AqBQBYpWxDvQBcgMhOB0oSuMDT74B08oLkNdMBYACWUcUBSyZtvWIABmCZywBYJi0Ae5x2x9B6Q3tNZb3aJYFJYBlVHLBk0pLAJLDeXACs15gEJoFlLgNgmbQkMAmsNxcA6zUmgUlgmcsAWCYtCUwC680FwHqNSWASWOYyAJZJSwKTwHpzAbBeYxKYBJa5DIBl0pLAJLDeXACs15gEJoFlLgNgmbQkMAmsNxcA6zUmgUlgmcsAWCYtCUwC680FwHqNSWASWOYyAJZJSwKTwHpzAbBeYxKYBJa5DIBl0pLAJLDeXACs15gEJoFlLgNgmbQkMAmsNxcA6zWudALfeOONYeHChXqVT7Rw+PDh5NUqF198caGvVqHdYobYQ+fPPvss7Nq1K+lg0W8asTZd38xgANu3qM+RI0cSgGfMmFEowLRbzAh76GzwVhbgoo9YTCmLAalKOld6Cg3AWqCqBJIp6dFfAOYstIxiD0N7geTVLgADMAD3SAGPAxYAA3CP7Du5Gg9DeyWhV7sADMBuAG/fvj0cO3Ys3HbbbWHKlClR+3H8+PGwdevWpGy77ap04ABgAI4CJ0uhTiBt2bIlLFu2LKl23rx5Yffu3VFNLF++PGzatCkpu3r16rB27dpJ2wFwlJQ9KeR6HZiz0D0Zw7aVdAJpw4YNYdWqVfVt169fH1auXNlxhxqht4L3339/eOONNwB448ZEg6L9bG0CsJahpPZ+TCSbCg8PD4exsbG6Avv27Qtz5sxpqcihQ4fCddddVy8/derUsHfv3jBz5kwABuACKOpTkJQ9Tztw7N+/P8ydO7e+CwblyMhIy/Xw/Pnzw549e+plt23bFhYvXtxy99PaVfXZo13WwKyBVX6OSv6YaXHzdLvd2rfWEQ+QvGY6AAzArgBb440npuz/N2/eHJYuXZrsV3NK2wmvHTt2dDxrDcCyIZ1UMWvgArTud0Pbeviaa64JBw8eTNSorW+nTZs2YZ3cad3bKGO/97eXQ04Ck8C99NOEuroByU5SzZo1q769Je1ZZ50V7Fpx7dNp3QvAnIWWGbmKa7Msa8Lm9XDjgKStewEYgAG4xwp0k8C1ppvXw/bvMeteAAbgHtt3cnVZDN2LnSpTu+3Ww62u97bTpkz9zTu+rIFZA+f1UNvts4K0ZMmS+trXrvXa2rebT9Z2u2mjVVmPdgEYgPP6FoBPKADAMiv9v2LPI5bHAGc5mdSrYcjaXxI4fgQ8/Wx7yXXg+LHKXDIrSJkbzJlIAByvPAAzhY53S5clsx44ADheaAAG4Hi3dFkyK8Br1qwJ69atS1rjJFZn0QEYgLvEMr54VoDtUlLtWeGHHnqo5SODnfYia7vxPWtd0qNdAAbgvL7t+VnovDvkAZLXyUIABuC8vABwzpN2eQYAgAE4j386blulJCSBZTaaWLHnEQtDFzPIVdLZ0882mq7XgXk7oRYoj7f1WY+q1C5vJ+TthDKKPd7WZ52pUru8nZA1sAzgKk1lWQPLbMQaGJCKMZeHzpVeAxf9Q9geA+yVDLRbzEEDgJlCy5zGAUsmbb1iAAZgmcsAWCYtAJsCTKG1BgNgrb5WOwlMAstcBsAyaUlgElhvLgDWa0wCk8AylwGwTFoSmATWmwuA9RqTwCSwzGUALJOWBCaB9eYCYL3GJDAJLHMZAMukJYFJYL25AFivMQlMAstcBsAyaUlgElhvLgDWa0wCk8AylwGwTFoSmATWmwuA9RqTwCSwzGUALJOWBCaB9eYCYL3GJDAJLHMZAMukJYFJYL25AFivMQlMAstcBsAyaUlgElhvLgDWa0wCk8AylwGwTFoSmATWmwuA9RqTwCSwzGUALJOWBCaB9eYCYL3GlU5g3k6oNViV3hJoSnr0l7cT8nZCGcVVekugiejRX95OyBpYBnCZptD//PNPGBkZSb72GR4eTr6nnnpqtD4e/a30FJo3M0R7M1NBD0Pbjsa2+91334WPP/44gfb333+vQ2t11GA+++yzw/Tp08Mtt9wSLrnkko46xLabScw2GwEwCdxLP02oy8PQsQBv3rw5fPPNNwmYlrTnn39+Sx1+/vnnMDo6Gj788MNw+eWXh6VLl7bVy6O/AAzAlQL4hx9+CE8//XS46aabwuLFi7vq+7Zt24KdNLLtL7zwwknbAnBXcmYr7HnE8hjg2ETKpmbnrfqtv0eOHAkvvvhieO6558I555yTqcu//vpreOKJJ8JTTz0VhoaG3Gccnn62zg+Mj4+PZ1Iy40aeHc5i6M8//zzYNK7xc/rpp4eFCxeGKVOmRKmQpd2oilMK9VO7lrzPP/98ePvtt9vu9fHjx8PWrVuTv1966aVhzpw5bcvefffd4ZlnngkXXHBBvYxHfz39DMAdANiyZUt4/PHHw9jYWNtSq1evDvZNA9nDWP2W/HfeeWeSvu2St1nvqVOnhj/++KOt9r/88kuSwu+88w4A9+JoH1uH5xErBiRLgfvuuy9s3749qkvz5s0LO3bs6AhxTLtRjXVZqF/atRNWZ5xxRss176FDh8Ltt98eDh48OKl3Nl0+99xz2/b6gw8+CH/99Ve49957kzIe/fX0Mwncwhrz588Pe/bsmfCXyy67rH4J488//5z0d0vhtWvXtjWah7G8DN3crl0qev3118Orr77aUh87s9wKXiu8b9++jtNoK/PAAw+ERx55JMyYMQOAuzzAZyruecRKA8mmccuWLav3y6Zxn3zyySQT/fbbb+Guu+6qg5w23UtrN5OQERv1Q7svvPBCuOqqq8L111/fco8HBwfbLlNiALaD7ZdffpksZTz66+lnErjJUmvWrAnr1q1L/tWg3Lt3b5g5c2ZL49kUe8mSJfW/dToX6GGsfknge+65J7ns0+46r50ktBNbdi34zDPPDKtWraprGgPwTz/9FJ599tnw1ltvAXDEQT13Ec8jVhpIth6zu8PsxJWtr9rBayIsX748bNq0CYBbOKKm84IFCwZuvvnm8Omnn0b5pnkGFAOwVWwPxezcuTPs2rUruaiyaNGigagGe1DI088kcMYBbDaancjavXs3a+ATCtQAnj59+kCn9W+zYFkBfvDBB4N9jx49CsAZPR29mecRKy2B0zphZ6htil2bZtfKpyVF3nbT9qvd373bHRgYGDh69GhykinmkxXgl19+OblfOoQAwDFC5ylTVoDbXe6w2/vSbgn0BqnIKWXj2huA85ASty13YkXo1JwMtomd5HrvvffCggULUmuoKsBMoVOtkbsAAHeQsN1NHbbmfffddzveZNBYbVUB5iRWbj5TKwDgNhLZ5Y077rhjwjVKS127rtnpkbZW1VUVYJu6p11GatQryxr4xx9/TO6xfvPNN7mMlIp7DwqUYQ28YcOGCdcjrdu2zn3ppZeiU5cE/u9yjt2hdvXVV4drr7021T1ZAP7iiy/CV199FR577DEATlW4BwX6HeBmeLOmLgD/B/D3338fXnvtteSb9skCsF2Pf/TRR8NFF10EwGkC9+Lv/QywnWmeNWtW1920e6U73fhR5Sm0iWlgnnbaaRPuXGslcrcAv//+++Hvv/8ONk1vPPtd5Fl3Tz9bn1kDNzip1dnmWJptim2XlFgDt34qyJ7ftbXqeeed11bSbgBuvIWyVqHHgRKA++gndewhhSuuuKLjM8Dt3Ld+/fqwcuVKAG7zWJ+dbLIH8Buf320Wa//+/WHu3Ln1f+50f7k9X2wnFKdNm1YvD8CxcZOjnOcRK2aA7dLRt99+m/Tw2LFjk36No1XX7Ub9TteDY9rNIWnbTfutXfulSfs5Hfs2gtfYAXugxMrdeuutLW+QseR98sknkwcYmn8Xy6O/nn5mCq2gpkWdHsbyWhOmtWsA2tNJN9xwQ/IgfzcfW/Pa44O2fasDgIfOANxHU+huzNRNWQ9jpYHUzf53Wzamv/b439dff50krd3H3PjbVo3t2dTbfk/Lflb2yiuvrJ+w6pdzDQAMwN3yEV0+BqToyrooGNvu4cOHw0cffWRPEQU7/2Agn3goIfk3+9pJL7tEZL8fbf/t9Iltt4uupBYFYABONUnWAh6Gzpr8//77bx1aq6MG8ymnnBLdfY/+Vhpg3k4Y7c1MBT3e1mc7WqV2eTshbyfMBGfMRh5v67P9qlK7vJ2QKXQMi5nKeEwps06hM3WwaSOP/lZ6Cs3bCXth2/Z1eBgagFdoB7Wpdm6lLEBuQCpAZH7YvRiRPaccgFTMGFdJZ08/22iSwAV4ukqGZgrNFFqGFCDJpJ1QcZV0JoE5Cy2jqkogeSU/AAMwAPdIAY8DFgADcI/sO7kaD0N7JaFXuwAMwADcIwU8DlgADMA9si8JDMAyK/2/Ys8jlscAe03taLcAM4cQPP3MdeBixtjl504BuJjBBWCm0DKnMeOQSVuvGIABWOYyAJZJC8CmAE8jaQ0GwFp9rXYSmASWuQyAZdKSwCSw3lwArNeYBCaBZS4DYJm0JDAJrDcXAOs1JoFJYJnLAFgmLQlMAuvNBcB6jUlgEljmMgCWSUsCk8B6cwGwXmMSmASWuQyAZdKSwCSw3lwArNeYBCaBZS4DYJm0JDAJrDcXAOs1rnQC83ZCrcGq9JZAU9Kjv7ydkLcTyiiu0lsCTUSP/vJ2QtbAMoCZQsukZQ3MGlhvLgDWa1zpNTAP9GsNBsBafa12AGYKLXMZAMukZQrNFFpvLgDWa0wCk8AylwGwTFoSmATWmwuA9RqTwCSwzGUALJOWBCaB9eYCYL3GJDAJLHMZAMukJYFJYL25AFivMQlMAstcBsAyaUlgElhvLgDWa0wCk8AylwGwTFoSmATWmwuA9RqTwCSwzGUALJOWBCaB9eYCYL3GJDAJLHMZAMukJYFJYL25AFivMQlMAstcBsAyaUlgElhvLgDWa0wCk8AylwGwTFoSmATWmwuA9RqTwCSwzGUALJOWBCaB9eYCYL3GJDAJLHMZAMukJYFJYL25AFivcaUTePbs2cG+RX3GxsbGx8fHw+Dg4EBRbVo7tFuM2h46HzhwINjXI5CszYHE0QV+Go9YBTabNDU0NJR0d3R0tFCAabeYkfbSuda7ot804gJwrbPDw8PFjCqtoEABCoyMjBTQyuQmCk/g2i5YEvNBgZNFgRUFnoxt1MwN4JNl4OgHCngqAMCe6tM2CuRUAIBzCsjmKOCpAAB7qk/bKJBTAQDOKSCbo4CnAgDsqT5to0BOBQA4p4BsjgKeCgCwp/q0jQI5FQDgnAKyOQp4KgDAnurTNgrkVACAcwrI5ijgqQAAe6pP2yiQUwEAzikgm6OApwIA7Kk+baNATgUAOKeAbI4CngoAsKf6tI0CORUA4JwCsjkKeCoAwJ7q0zYK5FQAgHMKyOYo4KkAAHuqT9sokFMBAM4pIJujgKcCAOypPm2jQE4FADingGyOAp4KALCn+rSNAjkVAOCcArI5CngqAMCe6tM2CuRUAIBzCsjmKOCpAAB7qk/bKJBTgf8B+RCwequcO6oAAAAASUVORK5CYII=) - 時刻 $ 0 $ では車1も車2も右に移動します。 - 時刻 $ 1 $ では車1は右に、車2は上に移動します。 - 時刻 $ 2 $ では車1は下に、車2は上に移動します。 - 時刻 $ 3 $ では車1は移動しません。車2は左に移動します。 - この出力によって得られるスコアは、以下のように計算されます。 - 車1の目的マスは $ (4,5) $ で、最終的な位置は $ (4,5) $ です。 - 車2の目的マスは $ (2,4) $ で、最終的な位置は $ (4,2) $ です。 - よって $ P_D $ は $ 20+\ (|4-4|+|5-5|)+(|2-4|+|4-2|)=24 $ です。 - $ P_T $ は $ 10\ +\ 4\ \times\ 0.01=10.04 $ です。 - このテストケースでの得点は $ 10^7\ /\ (24\ \times\ 10.04)\ =\ 41500.6… $ を切り上げた $ 41501 $ となります。 ### Sample Explanation 2 ジェネレータに $ seed=1 $ を指定することで同じ入力が得られます。