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