{"problem":{"name":"H. Programming a robot","description":{"content":"The last edition of the world robot conference took place in China last year, the most recent innovations on robots were on display. Those ranged from machines able to make people's portraits to robot","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10149H"},"statements":[{"statement_type":"Markdown","content":"The last edition of the world robot conference took place in China last year, the most recent innovations on robots were on display. Those ranged from machines able to make people's portraits to robots that can play soccer.\n\nWe want to program a robot, but a less sophisticated one. It takes only two commands:\n\nAt first, we just want to program this robot's movements. For that, we need you to print a sequence of commands to complete the following action: given the Cartesian coordinates of start and destination, and the initial direction the robot initially points to (North, South, East, or West), print a sequence of commands that takes the robot from its starting position to its destination.\n\nSince we are always concerned about efficiency, we wish the sequence to be as small as possible.\n\nThe input has one line with a pair of integers that indicate the starting coordinates, xo and yo, followed by a character that indicates a direction (_N_ for North, _S_ for South, _E_ for East, or _O_ for West). The next line contains a pair of integers indicating the destination coordinates, xd and yd.\n\nIn the first line, print the smallest size of a sequence of commands that take the robot from start to destination. In the next lines, print one of these sequences, one command per line. For the command Walk((k)), print \"A k\" (without the double quotes). For the command TurnRight(), print \"D\".\n\nIf there is more than one sequence of instructions that work, any one of them will be accepted.\n\n## Input\n\nThe input has one line with a pair of integers that indicate the starting coordinates, xo and yo, followed by a character that indicates a direction (_N_ for North, _S_ for South, _E_ for East, or _O_ for West). The next line contains a pair of integers indicating the destination coordinates, xd and yd.  0 ≤ xo, yo ≤ 5·105  0 ≤ xd, yd ≤ 5·105 \n\n## Output\n\nIn the first line, print the smallest size of a sequence of commands that take the robot from start to destination. In the next lines, print one of these sequences, one command per line. For the command Walk((k)), print \"A k\" (without the double quotes). For the command TurnRight(), print \"D\".If there is more than one sequence of instructions that work, any one of them will be accepted.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- $ n_k \\in \\mathbb{Z} $: number of digits ($1 \\leq n_k \\leq 10^6$)  \n- $ s_k \\in \\mathbb{Z} $: required sum of digits ($1 \\leq s_k \\leq 9 \\times 10^6$)  \n\nLet $ P(n, s) $ be the set of $ n $-digit palindromic numbers whose digits sum to $ s $.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 500 $  \n2. For each test case $ k $:  \n   - $ 1 \\leq n_k \\leq 10^6 $  \n   - $ 1 \\leq s_k \\leq 9 \\times 10^6 $  \n   - The first digit of the palindrome must be in $ \\{1, \\dots, 9\\} $ (no leading zeros)  \n\n**Objective**  \nFor each test case $ k $, find:  \n$$\n\\max P(n_k, s_k)\n$$  \nif $ P(n_k, s_k) \\neq \\emptyset $, otherwise output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10149H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}