<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

263. Towers
time limit per test: 1.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Vasya likes to play unusual games very much. One of these games is building towers. Unfortunately he is very tired today and instead of building towers himself, he wants his favorite robot to build towers for him. So, this time, Vasya will be laying on his couch sending commands to his robot.
The process of constructing towers is very easy. Imagine that you have a number of cells in a row. Cells are numbered from 1 to 10^6 and initially are empty. Robot can move to specified cell and put some number of cubes on it. If there are some cubes already on the cell, he will put new cubes on the top of the existing ones.
For two integers i and j (i <= j) the cubes on cells i..j are called 'tower', if on any cell with number k, i <= k <= j, there is a positive number of cubes, and there are no cubes on cell i-1 (or i is the leftmost cell in the row) and cell j+1 (or j is the rightmost cell in the row). Length of the tower is j-i+1 - the number of columns in it.
Within each tower the columns can be numbered from 1 to its length from the left to the right, so instead of giving robot a cell number, Vasya can give robot a tower number and column number within the tower.
As you can guess, your task is to write a robot that will process commands from Vasya. Robot must be able to build towers and respond to simple questions (see below).
Here is the list of available commands:

Actions:

put <x> <c> - put c cubes on cell x

tput <t> <x> <c> - put c cubes on column x in tower with number t (towers are numbered from left to the right)



Questions:

towers - print total number of towers built

cubes <t> - print the number of cubes in the tower t

length <t> - print the length of the tower t

tcubes <t> <x> - print the number of cubes in column x of the tower t

Input
The first line of input file contains a number of commands N (1 <= N <= 10^6). Each of the following N lines contains a command.
It's guaranteed that all input commands are correct (cell number c is always in range 1..10^6, tower t always exists, column x inside tower always exists and its corresponding cell number is also in range 1..10^6).
You can assume that no cell will have more than 2^31-1 cubes on it.

Output
For the commands that require printing, output exactly one line according to the format of sample output file below.
Please, do not follow English grammar rules and print '1 towers' instead of '1 tower'. The same applies for printing '1 cubes' and '1th', '2th' and '3th'.

Sample test(s)

Input
22
towers
put 2 5
put 1 6
put 3 6
put 3 3
towers
length 1
put 6 3
put 5 4
length 2
tcubes 2 1
tcubes 2 2
towers
cubes 1
cubes 2
put 4 3
towers
cubes 1
tput 1 6 50
cubes 1
tcubes 1 6
length 1

Output
0 towers
1 towers
length of 1th tower is 3
length of 2th tower is 2
4 cubes in 1th column of 2th tower
3 cubes in 2th column of 2th tower
2 towers
20 cubes in 1th tower
7 cubes in 2th tower
1 towers
30 cubes in 1th tower
80 cubes in 1th tower
53 cubes in 6th column of 1th tower
length of 1th tower is 6

Note
This problem has huge tests. Some read/write routines work very slow in several compilers (especially, C/C++: try to use getc() putc() functions to avoid IO troubles).
Author:	Roman V. Alekseenkov
Resource:	Saratov SU Contest: Golden Fall 2004
Date:	October 2, 2004

<|response|>
1. Abridged Problem Statement

There are 10^6 cells in a row, initially empty. Adding cubes to an empty cell makes it non-empty forever. A tower is a maximal contiguous segment of non-empty cells.

Process up to 10^6 commands:

- put x c: add c cubes to global cell x.
- tput t x c: add c cubes to column x of the t-th tower.
- towers: print the number of towers.
- cubes t: print total cubes in the t-th tower.
- length t: print length of the t-th tower.
- tcubes t x: print cubes in column x of the t-th tower.

Towers are numbered from left to right. Columns inside a tower are also numbered from left to right.

2. Key Observations

Observation 1: Towers never split
Cubes are only added, never removed. Therefore:
- an empty cell may become non-empty;
- a non-empty cell stays non-empty forever;
- towers can appear, extend, or merge;
- towers never split.
This makes the structure much easier to maintain.

Observation 2: A tower can be represented by one interval
For every current tower, store its left boundary, right boundary, and total number of cubes in the tower. Also keep height[x] = number of cubes on global cell x. Since x <= 10^6, a simple array is enough.

Observation 3: We need order statistics
Commands refer to the t-th tower from the left. So we need a data structure that supports:
- ordered towers by left boundary;
- finding the k-th tower;
- inserting a new tower;
- deleting a merged tower;
- finding predecessor tower by position.
A randomized treap with subtree sizes is a good fit. Each treap node represents one tower and is keyed by the tower's left endpoint. (In the implementation below the treap is a generic, reusable template.)

3. Full Solution Approach

Maintain an order-statistic treap. Each node stores:
- key = left endpoint of tower
- rightEnd (data.end) = right endpoint of tower
- sum (data.sum) = total cubes in this tower
- size = number of nodes in subtree
Also maintain height[1..10^6].

Query: towers
The answer is the number of nodes in the treap: size[root].

Query: length t
Find the t-th tower in the treap. If its interval is [l, r], print r - l + 1.

Query: cubes t
Find the t-th tower and print its stored sum.

Query: tcubes t x
Find the t-th tower. If it starts at l, then column x corresponds to global cell cell = l + x - 1. Print height[cell].

Update: tput t x c
Find the t-th tower. Convert local column x to a global cell: cell = tower.left + x - 1. Then height[cell] += c and tower.sum += c. This does not change tower boundaries because the cell is already inside an existing tower.

Update: put x c
This is the only operation that can change tower structure.

Case 1: height[x] > 0
Cell x is already occupied. Only update height[x] += c and containingTower.sum += c. The containing tower is the tower with largest left endpoint <= x.

Case 2: height[x] == 0
Cell x becomes occupied. Check its neighbors:
  leftOccupied  = height[x - 1] > 0
  rightOccupied = height[x + 1] > 0
There are four cases.

Case 2.1: neither neighbor is occupied
Create a new tower [x, x]; insert a new treap node.

Case 2.2: only left neighbor is occupied
Extend the left tower [..., x - 1] -> [..., x]: update its right endpoint and sum.

Case 2.3: only right neighbor is occupied
Extend the right tower to the left [x + 1, ...] -> [x, ...]. The right tower starts at x + 1; change its key from x + 1 to x. This is safe because x - 1 is empty, so no other tower start lies between x and x + 1.

Case 2.4: both neighbors are occupied
Cell x connects two towers [left tower] x [right tower]. Merge them:
  left.rightEnd = right.rightEnd
  left.sum += c + right.sum
  erase right tower

Complexity
Let T be the current number of towers. Each treap operation is expected O(log T), so each command is processed in expected O(log T). Memory usage is O(10^6 + number of created tower nodes).

4. C++ Implementation

```cpp
#include <bits/stdc++.h>
// #include <coding_library/data_structures/treap.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<class KeyT, class T, T (*merge_func)(T, T), uint64_t (*rng)()>
struct TreapNode {
    KeyT key;
    T data, subtree;
    uint64_t prior;
    size_t size;
    TreapNode *left, *right;

    TreapNode(KeyT key, T data)
        : key(key), data(data), left(nullptr), right(nullptr), size(1) {
        prior = rng();
    }

    void pull() {
        subtree = data;
        size = 1;
        if(left) {
            subtree = merge_func(left->subtree, subtree);
            size += left->size;
        }
        if(right) {
            subtree = merge_func(subtree, right->subtree);
            size += right->size;
        }
    }

    friend pair<TreapNode*, TreapNode*> split(TreapNode* t, KeyT key) {
        if(!t) {
            return {nullptr, nullptr};
        }
        if(key < t->key) {
            auto [left, t_left] = split(t->left, key);
            t->left = t_left;
            t->pull();
            return {left, t};
        } else {
            auto [t_right, right] = split(t->right, key);
            t->right = t_right;
            t->pull();
            return {t, right};
        }
    }

    friend pair<TreapNode*, TreapNode*> split_by_size(
        TreapNode* t, size_t size
    ) {
        if(!t) {
            return {nullptr, nullptr};
        }

        size_t left_size = t->left ? t->left->size : 0;
        if(left_size >= size) {
            auto [left, t_left] = split_by_size(t->left, size);
            t->left = t_left;
            t->pull();
            return {left, t};
        } else {
            auto [t_right, right] =
                split_by_size(t->right, size - 1 - left_size);
            t->right = t_right;
            t->pull();
            return {t, right};
        }
    }

    friend TreapNode* merge(TreapNode* l, TreapNode* r) {
        if(!l || !r) {
            return l ? l : r;
        } else if(l->prior > r->prior) {
            l->right = merge(l->right, r);
            l->pull();
            return l;
        } else {
            r->left = merge(l, r->left);
            r->pull();
            return r;
        }
    }

    friend TreapNode* unordered_merge(TreapNode* l, TreapNode* r) {
        if(!l) {
            return r;
        }
        if(!r) {
            return l;
        }
        if(l->prior < r->prior) {
            swap(l, r);
        }
        auto [t1, t2] = split(r, l->key);
        l->left = unordered_merge(l->left, t1);
        l->right = unordered_merge(l->right, t2);
        l->pull();
        return l;
    }

    friend void insert_in(TreapNode*& t, TreapNode* it) {
        if(!t) {
            t = it;
        } else if(it->prior > t->prior) {
            auto [t1, t2] = split(t, it->key);
            it->left = t1;
            it->right = t2;
            t = it;
        } else {
            insert_in(it->key < t->key ? t->left : t->right, it);
        }
        t->pull();
    }

    friend TreapNode* erase_from(
        TreapNode*& t, KeyT key, bool delete_node = false
    ) {
        T return_data;
        if(t->key == key) {
            auto tmp = t;
            t = merge(t->left, t->right);

            return_data = tmp->data;
            if(delete_node) {
                delete tmp;
                return_data = nullptr;
            }
        } else {
            return_data =
                erase_from(key < t->key ? t->left : t->right, key, delete_node);
        }
        if(t) {
            t->pull();
        }
        return return_data;
    }
};

template<class KeyT, class T, T (*merge_func)(T, T)>
class Treap {
  public:
    static uint64_t rng() {
        static mt19937_64 static_rng(random_device{}());
        return static_rng();
    }

    using Node = TreapNode<KeyT, T, merge_func, Treap::rng>;

    void _pull_all(Node* t) {
        if(t) {
            _pull_all(t->left);
            _pull_all(t->right);
            t->pull();
        }
    }

    Node* root;

    Treap() { root = nullptr; }
    Treap(const vector<pair<KeyT, T>>& a) { build_cartesian_tree(a); }

    void build_cartesian_tree(const vector<pair<KeyT, T>>& a) {
        vector<Node*> st;

        function<Node*(Node*)> recycle_stack = [&](Node* last) {
            Node* new_last = st.back();
            st.pop_back();
            new_last->right = last;
            return new_last;
        };

        for(const auto& [key, val]: a) {
            Node* new_node = new Node(key, val);
            Node* last = nullptr;
            while(!st.empty() && st.back()->prior < new_node->prior) {
                last = recycle_stack(last);
            }

            new_node->left = last;
            st.push_back(new_node);
        }

        root = nullptr;
        while(!st.empty()) {
            root = recycle_stack(root);
        }

        _pull_all(root);
    }

    void insert(KeyT key, T data) {
        Node* new_node = new Node(key, data);
        insert_in(root, new_node);
    }

    Node* erase(KeyT key) { return erase_from(root, key); }

    friend Treap<KeyT, T, merge_func> merge_treaps(
        Treap<KeyT, T, merge_func> l, Treap<KeyT, T, merge_func> r
    ) {
        Treap<KeyT, T, merge_func> res;
        res.root = unordered_merge(l.root, r.root);
        return res;
    }

    int count_leq(KeyT max_key) {
        int cnt = 0;
        Node* cur = root;
        while(cur) {
            if(cur->key <= max_key) {
                cnt += (cur->left ? cur->left->size : 0) + 1;
                cur = cur->right;
            } else {
                cur = cur->left;
            }
        }
        return cnt;
    }
};

struct Tower {
    int end;
    int64_t sum;
};

Tower merge_tower(Tower a, Tower b) { return a; }

using TowerTreap = Treap<int, Tower, merge_tower>;
using Node = TowerTreap::Node;

Node* kth_tower(Node* t, int k) {
    while(t) {
        int left_size = t->left ? (int)t->left->size : 0;
        if(k < left_size) {
            t = t->left;
        } else if(k == left_size) {
            return t;
        } else {
            k -= left_size + 1;
            t = t->right;
        }
    }
    return nullptr;
}

Node* find_node(Node* t, int key) {
    while(t) {
        if(t->key == key) {
            return t;
        }
        t = key < t->key ? t->left : t->right;
    }
    return nullptr;
}

Node* pred_node(Node* t, int x) {
    Node* res = nullptr;
    while(t) {
        if(t->key <= x) {
            res = t;
            t = t->right;
        } else {
            t = t->left;
        }
    }
    return res;
}

void erase_node(Node*& t, int key) {
    if(t->key == key) {
        Node* tmp = t;
        t = merge(t->left, t->right);
        delete tmp;
    } else {
        erase_node(key < t->key ? t->left : t->right, key);
    }
    if(t) {
        t->pull();
    }
}

namespace fastio {
constexpr int BUF_SIZE = 1 << 16;
char buf[BUF_SIZE];
int buf_pos = 0, buf_len = 0;

int get_char() {
    if(buf_pos == buf_len) {
        buf_len = (int)fread(buf, 1, BUF_SIZE, stdin);
        buf_pos = 0;
    }
    return buf_pos < buf_len ? (unsigned char)buf[buf_pos++] : EOF;
}

int skip_ws() {
    int c = get_char();
    while(c == ' ' || c == '\n' || c == '\r' || c == '\t') {
        c = get_char();
    }
    return c;
}

int read_int() {
    int c = skip_ws();
    int sign = 1;
    if(c == '-') {
        sign = -1;
        c = get_char();
    } else if(c == '+') {
        c = get_char();
    }
    int x = 0;
    while(c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = get_char();
    }
    return sign * x;
}

int read_word(char* s) {
    int c = skip_ws();
    int len = 0;
    while(c != EOF && c != ' ' && c != '\n' && c != '\r' && c != '\t') {
        s[len++] = (char)c;
        c = get_char();
    }
    s[len] = 0;
    return len;
}

constexpr int OUT_SIZE = 1 << 22;
char out_buf[OUT_SIZE];
int out_pos = 0;

void flush_out() {
    fwrite(out_buf, 1, out_pos, stdout);
    out_pos = 0;
}

void put_char(char c) {
    if(out_pos == OUT_SIZE) {
        flush_out();
    }
    out_buf[out_pos++] = c;
}

void put_str(const char* s) {
    while(*s) {
        put_char(*s++);
    }
}

void put_int(int64_t x) {
    if(x < 0) {
        put_char('-');
        x = -x;
    }
    char tmp[24];
    int n = 0;
    if(x == 0) {
        tmp[n++] = '0';
    }
    while(x) {
        tmp[n++] = (char)('0' + x % 10);
        x /= 10;
    }
    while(n) {
        put_char(tmp[--n]);
    }
}

void put_ordinal(int64_t x) {
    put_int(x);
    put_str("th");
}
}  // namespace fastio

int n;
int height[1000002];
TowerTreap towers;

void do_put(int x, int cubes) {
    Node*& root = towers.root;
    if(height[x] > 0) {
        height[x] += cubes;
        pred_node(root, x)->data.sum += cubes;
        return;
    }

    height[x] = cubes;
    bool left = height[x - 1] > 0;
    bool right = height[x + 1] > 0;
    if(!left && !right) {
        towers.insert(x, Tower{x, (int64_t)cubes});
    } else if(left && !right) {
        Node* lt = pred_node(root, x - 1);
        lt->data.end = x;
        lt->data.sum += cubes;
    } else if(!left && right) {
        Node* rt = find_node(root, x + 1);
        rt->key = x;
        rt->data.sum += cubes;
    } else {
        Node* lt = pred_node(root, x - 1);
        Node* rt = find_node(root, x + 1);
        lt->data.end = rt->data.end;
        lt->data.sum += (int64_t)cubes + rt->data.sum;
        erase_node(root, x + 1);
    }
}

void read() { n = fastio::read_int(); }

void solve() {
    // Cubes are only ever added, never removed, so a filled cell stays filled
    // and a tower can only grow or merge with a neighbour - it never splits.
    // That lets us keep the towers in a treap keyed by their starting cell,
    // one node per tower, while a flat height[] array (cells go up to 10^6)
    // holds the cubes standing on each individual column.
    //
    // Each tower node stores its end cell and its total cube count, so 'cubes'
    // and 'length' of the t-th tower are answered by an order-statistic lookup
    // (the k-th tower by subtree size) reading a single node, and 'towers' is
    // just the number of nodes in the treap.
    //
    // A 'put x c' on an already filled cell only bumps that cell's height and
    // the sum of the tower containing it. On an empty cell we inspect the two
    // neighbours x-1 and x+1: with neither filled we insert a fresh length-one
    // tower; with only the left filled we extend that tower's end to x; with
    // only the right filled we relabel that tower's start down to x by editing
    // its node key, which keeps the BST order because x-1 is empty; with both
    // filled we bridge them, folding the right tower's end and sum into the
    // left node and erasing the right one. 'tput' and 'tcubes' map column x of
    // tower t to cell start+x-1 and reuse the per-cell height.

    char cmd[8];
    for(int i = 0; i < n; i++) {
        fastio::read_word(cmd);
        Node* root = towers.root;
        if(cmd[0] == 'p') {
            int x = fastio::read_int();
            int c = fastio::read_int();
            do_put(x, c);
        } else if(cmd[0] == 'c') {
            int t = fastio::read_int();
            Node* nd = kth_tower(root, t - 1);
            fastio::put_int(nd->data.sum);
            fastio::put_str(" cubes in ");
            fastio::put_ordinal(t);
            fastio::put_str(" tower\n");
        } else if(cmd[0] == 'l') {
            int t = fastio::read_int();
            Node* nd = kth_tower(root, t - 1);
            fastio::put_str("length of ");
            fastio::put_ordinal(t);
            fastio::put_str(" tower is ");
            fastio::put_int(nd->data.end - nd->key + 1);
            fastio::put_char('\n');
        } else if(cmd[1] == 'o') {
            fastio::put_int(root ? (int64_t)root->size : 0);
            fastio::put_str(" towers\n");
        } else if(cmd[1] == 'p') {
            int t = fastio::read_int();
            int x = fastio::read_int();
            int c = fastio::read_int();
            Node* nd = kth_tower(root, t - 1);
            height[nd->key + x - 1] += c;
            nd->data.sum += c;
        } else {
            int t = fastio::read_int();
            int x = fastio::read_int();
            Node* nd = kth_tower(root, t - 1);
            fastio::put_int(height[nd->key + x - 1]);
            fastio::put_str(" cubes in ");
            fastio::put_ordinal(x);
            fastio::put_str(" column of ");
            fastio::put_ordinal(t);
            fastio::put_str(" tower\n");
        }
    }

    fastio::flush_out();
}

int main() {
    int T = 1;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

5. Python Implementation

Python is included for clarity and education. The original limits are quite tight, so C++ is the safer choice for actual submission.

```python
import sys
import random
from array import array

# ------------------------------------------------------------
# Fast scanner.
# It reads the whole input once and parses tokens manually.
# This avoids creating a huge list with split().
# ------------------------------------------------------------

class FastScanner:
    def __init__(self):
        self.data = sys.stdin.buffer.read()
        self.i = 0
        self.n = len(self.data)

    def next_token(self):
        data = self.data
        n = self.n
        i = self.i

        while i < n and data[i] <= 32:
            i += 1

        j = i
        while j < n and data[j] > 32:
            j += 1

        self.i = j
        return data[i:j]

    def next_int(self):
        data = self.data
        n = self.n
        i = self.i

        while i < n and data[i] <= 32:
            i += 1

        x = 0
        while i < n and data[i] > 32:
            x = x * 10 + data[i] - 48
            i += 1

        self.i = i
        return x


# ------------------------------------------------------------
# Treap stored in compact arrays.
#
# Node index 0 means null.
#
# For node v:
#   key[v]   = starting cell of tower
#   end[v]   = ending cell of tower
#   sumv[v]  = total cubes in tower
#   left[v]  = left child
#   right[v] = right child
#   size[v]  = subtree size
#   prio[v]  = random priority
# ------------------------------------------------------------

key = array("i", [0])
end = array("i", [0])
sumv = array("q", [0])
left = array("i", [0])
right = array("i", [0])
size = array("i", [0])
prio = array("Q", [0])

# Deterministic xorshift RNG for treap priorities.
seed = 88172645463393265


def rng():
    global seed
    seed ^= (seed << 7) & ((1 << 64) - 1)
    seed ^= seed >> 9
    return seed & ((1 << 64) - 1)


def new_node(k, r, s):
    """Create a new treap node and return its index."""
    idx = len(key)

    key.append(k)
    end.append(r)
    sumv.append(s)
    left.append(0)
    right.append(0)
    size.append(1)
    prio.append(rng())

    return idx


def pull(v):
    """Recalculate subtree size of node v."""
    size[v] = 1 + size[left[v]] + size[right[v]]


sys.setrecursionlimit(2_000_000)


def split(t, k):
    """
    Split treap t into:
      a: all nodes with key <= k
      b: all nodes with key > k
    """
    if t == 0:
        return 0, 0

    if k < key[t]:
        a, b = split(left[t], k)
        left[t] = b
        pull(t)
        return a, t
    else:
        a, b = split(right[t], k)
        right[t] = a
        pull(t)
        return t, b


def merge(a, b):
    """Merge two treaps where every key in a is <= every key in b."""
    if a == 0 or b == 0:
        return a or b

    if prio[a] > prio[b]:
        right[a] = merge(right[a], b)
        pull(a)
        return a
    else:
        left[b] = merge(a, left[b])
        pull(b)
        return b


def insert(t, v):
    """Insert node v into treap t and return new root."""
    if t == 0:
        return v

    if prio[v] > prio[t]:
        a, b = split(t, key[v])
        left[v] = a
        right[v] = b
        pull(v)
        return v

    if key[v] < key[t]:
        left[t] = insert(left[t], v)
    else:
        right[t] = insert(right[t], v)

    pull(t)
    return t


def erase(t, k):
    """Erase node with key k from treap t and return new root."""
    if key[t] == k:
        return merge(left[t], right[t])

    if k < key[t]:
        left[t] = erase(left[t], k)
    else:
        right[t] = erase(right[t], k)

    pull(t)
    return t


def kth(t, k):
    """Return index of zero-based k-th node by key order."""
    while t:
        ls = size[left[t]]

        if k < ls:
            t = left[t]
        elif k == ls:
            return t
        else:
            k -= ls + 1
            t = right[t]

    return 0


def find_node(t, k):
    """Find node with exact key k."""
    while t:
        if key[t] == k:
            return t
        if k < key[t]:
            t = left[t]
        else:
            t = right[t]
    return 0


def pred_node(t, x):
    """Find node with maximum key <= x."""
    ans = 0

    while t:
        if key[t] <= x:
            ans = t
            t = right[t]
        else:
            t = left[t]

    return ans


# ------------------------------------------------------------
# Main command processing.
# ------------------------------------------------------------

def main():
    scanner = FastScanner()

    n = scanner.next_int()

    # height[x] = cubes in global cell x.
    # Use 1_000_002 so x-1 and x+1 are safe for x in [1, 10^6].
    height = array("i", [0]) * 1_000_002

    root = 0

    out = []

    def ordinal(x):
        return str(x) + "th"

    def do_put(x, c):
        nonlocal root

        # If cell already belongs to a tower, only heights and sums change.
        if height[x] > 0:
            height[x] += c
            v = pred_node(root, x)
            sumv[v] += c
            return

        # Cell becomes non-empty.
        height[x] = c

        has_left = height[x - 1] > 0
        has_right = height[x + 1] > 0

        if not has_left and not has_right:
            # New isolated tower [x, x].
            root = insert(root, new_node(x, x, c))

        elif has_left and not has_right:
            # Extend the left tower to the right.
            lt = pred_node(root, x - 1)
            end[lt] = x
            sumv[lt] += c

        elif not has_left and has_right:
            # Extend the right tower to the left.
            rt = find_node(root, x + 1)
            key[rt] = x
            sumv[rt] += c

        else:
            # Merge left tower, new cell x, and right tower.
            lt = pred_node(root, x - 1)
            rt = find_node(root, x + 1)

            end[lt] = end[rt]
            sumv[lt] += c + sumv[rt]

            root = erase(root, x + 1)

    for _ in range(n):
        cmd = scanner.next_token()

        if cmd[0] == ord("p"):
            # put x c
            x = scanner.next_int()
            c = scanner.next_int()
            do_put(x, c)

        elif cmd[0] == ord("c"):
            # cubes t
            t = scanner.next_int()
            v = kth(root, t - 1)
            out.append(f"{sumv[v]} cubes in {ordinal(t)} tower\n")

        elif cmd[0] == ord("l"):
            # length t
            t = scanner.next_int()
            v = kth(root, t - 1)
            length = end[v] - key[v] + 1
            out.append(f"length of {ordinal(t)} tower is {length}\n")

        elif cmd[1] == ord("o"):
            # towers
            out.append(f"{size[root]} towers\n")

        elif cmd[1] == ord("p"):
            # tput t x c
            t = scanner.next_int()
            x = scanner.next_int()
            c = scanner.next_int()

            v = kth(root, t - 1)
            cell = key[v] + x - 1

            height[cell] += c
            sumv[v] += c

        else:
            # tcubes t x
            t = scanner.next_int()
            x = scanner.next_int()

            v = kth(root, t - 1)
            cell = key[v] + x - 1

            out.append(
                f"{height[cell]} cubes in {ordinal(x)} column of {ordinal(t)} tower\n"
            )

    sys.stdout.write("".join(out))


if __name__ == "__main__":
    main()
```
