The street in front of you has some empty parking spots. A car needs 1 parking spot to park; an SUV needs 2 parking spots; and an 18-wheeler truck needs 4. Some parking spots are already taken. Given a description of the parking spots that are free and taken in the street currently, compute in how many different ways you can fill up the street with vehicles (cars, SUVs, or 18-wheelers).

For instance, in the following street, where a dash (-) means an empty spot and an X means a spot already taken,

You might already know that, in most modern C++ compilers, int is a 32-bit integer, so it can store numbers from $$$-2^{31}$$$ (-2147483648) to $$$2^{31}-1$$$ (2147483647). If you use long long you can store 64-bit integers (around 18 digits long), but if you want to work with numbers longer than that, you are on your own.

In this problem we ask you to write code that can add arbitrarily long positive integers, and that can read and write them in the standard form (base 10 representation).

Your first instinct might be to use strings: every digit in your number is a char from '0' to '9'. This works great for input and output, but sums are kind of slow because your program must add digit by digit.

Your second instinct might be to use vector<int>, and make every number of your vector a "big-digit" in base $$$2^{31}$$$ (or $$$2^{32}$$$ if you know how to use unsigned ints). You can add two "big-digits" by transforming them first into "long long". Now sums are fast: every time you add up two "big-digits" you are adding a bit more than 9 of the old base-10 digits. But reading and writing requires translating base 10 numbers into base $$$2^{31}$$$ or $$$2^{32}$$$, which is not a trivial task.

Let's hope you have a third instinct that will allow you to solve this problem.

Did you solve the previous problem? You surely realized that treaps don't seem more useful than a regular std::set. This is going to change now.

Since we have implemented the treaps ourselves, we can easily extend them to do more things. The situation is very similar to segment trees: they are not just useful to store individual elements, but they can also store additional information that allows us to do bulk queries or updates faster.

We will ask you to implement the easiest of those extensions for treaps: compute the order of an element, and find the element with a given order. The order of an element of key $$$k$$$ is its (0-based) index when you traverse the treap in preorder (that is, from smaller to largest key, or from left to right). If you are familiar with GNU C++ STL PBDS containers, you might know these operations as order_of_key and find_by_order.

How can we implement this in logarithmic time? Make every node have its size precomputed, where the size of a node is just the number of nodes of the subtreap rooted at it. To find the element of order $$$t$$$ in a treap, compare $$$t$$$ with the size of the root's left child: if the size is larger than $$$t$$$, the element must be in the left child; if the size is exactly $$$t$$$, the element is the root; if the size is less than $$$t$$$, the element is in the right child.

The only difficulty is to make sure that, whenever split and join operations modify the treaps, these precomputed sizes don't get outdated. To show us that you can handle that, we will ask you to write a program that implements the following operations efficiently.

• ADD $$$k$$$ $$$h$$$: Add a node $$$K$$$ with key $$$k$$$ and height $$$h$$$ into the treap. Use 1 split and 2 joins.
• DEL $$$k$$$: Delete the node with key $$$k$$$ from the treap $$$T$$$, using 2 splits and 1 join.
• ORDER_OF_KEY $$$k$$$: Find the order of the key $$$k$$$, or $$$-1$$$ if it does not exist.
• FIND_BY_ORDER $$$i$$$: Find the key of order $$$i\geq 0$$$, or $$$-1$$$ if the treap has $$$i$$$ elements or fewer.