Antitest

You are given an implementation of a Cartesian tree. There's nothing wrong with the implementation itself, so no need to worry. However, there's a unique aspect: instead of using y-values in the Merge operation, the function rnd.next(2) is used, which returns a random number between 0 and 1. It is suggested that a tree built this way might end up with excessive depth. Your task is to devise a sequence of no more than 3000 operations that results in a tree with a depth of at least 1000 (note that a tree with a single vertex has a depth of 1).

"'cpp 1 typedef struct tree *ptree;

2 struct tree ptree l, r; int x; ;

3 ptree root, a, b, c;

// comment: l = y < x, r = y >= x

6 void Split(ptree t, ptree l, ptree r, int x)

7 if (t == 0) l = r = 0;

8 else if (t->x >= x) Split(t->l, l, t->l, x), r = t;

9 else Split(t->r, t->r, r, x), l = t;

10

11 void Merge(ptree t, ptree l, ptree r)

12 if (l == 0) t = r;

13 else if (r == 0) t = l;

14 else if (rnd.next(2)) t = l, Merge(t->r, t->r, r);

15 else t = r, Merge(t->l, l, t->l);

16

17 void Add(int x)

18 b = new tree(x);

19 Split(root, a, c, x);

20 Merge(a, a, b);

21 Merge(root, a, c);

22

23 void Del(int x)

24 Split(root, a, b, x);

25 Split(b, b, c, x + 1);

26 Merge(root, a, c);

27

"'

Input

You start with an entirely empty file. The tree is initially empty as well.

A sequence of operations in the form of ADD x and DEL x.

- ADD x invokes the function Add(x) (refer to the implementation). - DEL x invokes the function Del(x) (refer to the implementation).

Examples

Note

The checker uses a Random function that is independent of time, meaning identical solutions will always yield the same result. If you receive a PE (Presentation Error), your output is not a valid sequence of no more than 3000 operations. If you receive a WA (Wrong Answer), the sequence of operations is valid, but the resulting tree's depth is less than 1000.