Negative Time Summation
Contest: Codeforces Round 522 (Div. 1, based on Technocup 2019 Elimination Round 3)
Difficulty rating: 3400
Tags: constructive algorithms

Everyone knows that computers become faster and faster. Recently Berland scientists have built a machine that can move itself back in time!

More specifically, it works as follows. It has an infinite grid and a robot which stands on one of the cells. Each cell of the grid can either be empty or contain 0 or 1. The machine also has a program which consists of instructions, which are being handled one by one. Each instruction is represented by exactly one symbol (letter or digit) and takes exactly one unit of time (say, second) to be performed, except the last type of operation (it's described below). Here they are:

- 0 or 1: the robot places this number into the cell he is currently at. If this cell wasn't empty before the operation, its previous number is replaced anyway.
- e: the robot erases the number into the cell he is at.
- l, r, u or d: the robot goes one cell to the left/right/up/down.
- s: the robot stays where he is for a unit of time.
- t: let $$$x$$$ be $$$0$$$, if the cell with the robot is empty, otherwise let $$$x$$$ be one more than the digit in this cell (that is, $$$x = 1$$$ if the digit in this cell is $$$0$$$, and $$$x = 2$$$ if the digit is $$$1$$$). Then the machine travels $$$x$$$ seconds back in time. Note that this doesn't change the instructions order, but it changes the position of the robot and the numbers in the grid as they were $$$x$$$ units of time ago. You can consider this instruction to be equivalent to a Ctrl-Z pressed $$$x$$$ times.

For example, let the board be completely empty, and the program be sr1t0. Let the robot initially be at $$$(0, 0)$$$.

- [now is the moment $$$0$$$, the command is s]: we do nothing.
- [now is the moment $$$1$$$, the command is r]: we are now at $$$(1, 0)$$$.
- [now is the moment $$$2$$$, the command is 1]: we are at $$$(1, 0)$$$, and this cell contains $$$1$$$.
- [now is the moment $$$3$$$, the command is t]: we travel $$$1 + 1 = 2$$$ moments back, that is, to the moment $$$1$$$.
- [now is the moment $$$1$$$, the command is 0]: we are again at $$$(0, 0)$$$, and the board is clear again, but after we follow this instruction, this cell has $$$0$$$ in it. We've just rewritten the history. The consequences of the third instruction have never happened.

Now Berland scientists want to use their machine in practice. For example, they want to be able to add two integers.

Assume that the initial state of the machine is as follows:

- One positive integer is written in binary on the grid in such a way that its right bit is at the cell $$$(0, 1)$$$, from left to right from the highest bit to the lowest bit.
- The other positive integer is written in binary on the grid in such a way that its right bit is at the cell $$$(0, 0)$$$, from left to right from the highest bit to the lowest bit.
- All the other cells are empty.
- The robot is at $$$(0, 0)$$$.
- We consider this state to be always in the past; that is, if you manage to travel to any negative moment, the board was always as described above, and the robot was at $$$(0, 0)$$$ for eternity.

You are asked to write a program after which

- The robot stands on a non-empty cell,
- If we read the number starting from the cell with the robot and moving to the right until the first empty cell, this will be $$$a + b$$$ in binary, from the highest bit to the lowest bit.

Note that there are no restrictions on other cells. In particular, there may be a digit just to the left to the robot after all instructions.

In each test you are given up to $$$1000$$$ pairs $$$(a, b)$$$, and your program must work for all these pairs. Also since the machine's memory is not very big, your program must consist of no more than $$$10^5$$$ instructions.

Input format:
The first line contains the only integer $$$t$$$ ($$$1\le t\le 1000$$$) standing for the number of testcases. Each of the next $$$t$$$ lines consists of two positive integers $$$a$$$ and $$$b$$$ ($$$1\le a, b < 2^{30}$$$) in decimal.

Output format:
Output the only line consisting of no more than $$$10^5$$$ symbols from 01eslrudt standing for your program.

Note that formally you may output different programs for different tests.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
2
123456789 987654321
555555555 555555555

Example output:
0l1l1l0l0l0l1l1l1l0l1l0l1l1l0l0l0l1l0l1l1l1l0l0l0l1l0l0l0l0l1l0lr

Editorial:
Disclaimer: there seem to be solutions much simpler than the author's. You can read some passed codes.
Let's define our workplace as follows: we will take 6 rows, containing (in order from up to down): carry bits, bits of $$$a$$$, bits of $$$b$$$, two lines of some buffer garbage and the line with the answer. Consequently, these strings have $$$y$$$-coordinates from $$$2$$$ to $$$-3$$$.
Now our plan is to do the following:
• add leading zeroes to the left of $$$a$$$ and $$$b$$$,
• go back to the right end of numbers,
• a little more than $$$30$$$ times (say, $$$32$$$) do the following:   add a zero carry bit, if necessary,  calculate $$$xor(carry, a_i, b_i)$$$, which is the $$$i$$$-th digit of the result,  calculate $$$maj(carry, a_i, b_i)$$$, which is the new carry ($$$maj$$$ is the majority function which returns $$$1$$$ iff at least $$$2$$$ of $$$3$$$ arguments are $$$1$$$),  move one cell to the left to the next digits.
• add a zero carry bit, if necessary,
• calculate $$$xor(carry, a_i, b_i)$$$, which is the $$$i$$$-th digit of the result,
• calculate $$$maj(carry, a_i, b_i)$$$, which is the new carry ($$$maj$$$ is the majority function which returns $$$1$$$ iff at least $$$2$$$ of $$$3$$$ arguments are $$$1$$$),
• move one cell to the left to the next digits.
To do this we can implement some helper functions. Let inv(dir) be the direction opposite to dir (for example, inv(l) = r):
move_if_1(dir) = <dir><inv(dir)>st
This means that after running the subprogram, say, lrst, robot goes one cell to the left iff it was standing on $$$1$$$, otherwise it doesn't do anything. Let's write some other subprograms:
move_if_0(dir) = <dir><inv(dir)>t
move_if_not_empty(dir) = <dir>s<inv(dir)>t
copy(dir) = <dir>10<inv(dir)>t
The last subprogram copies a symbol one cell to the given direction. It's important that it's the first function which works properly only when the robot is standing on a non-empty cell.
Explaining how to build a maj and xor of three arguments seems really hard to me, but the idea is as follows: we (ab)use the fact that these functions are symmetric (that is, their result doesn't depend on the order of the arguments), so if we have three bits one under another and we want to obtain some $$$f(x, y, z)$$$ somewhere under them, we can first copy them one, two and three times, respectively, place necessary bits in the buffer zone and then do something like
move_if_1(r) d move_if_1(r) d move_if_1(r) d do_something
In the end we should obtain something like this (if numbers were no more than two bits long):