While traveling through the gaming universe, Ralph and Vanellope discovered an amazing game. In this game, you need to count very quickly, which they really liked. The action of the game takes place around a magical apple tree.

Initially, the apple tree consists of only one apple - the root. The number of this apple is 1. After that, Ralph adds a new apple, which he links to an existing one using a branch. On each branch, Ralph writes down a letter of the Latin alphabet from a to z.

Vanellope, in turn, sometimes plucks some apple. Together with the apple, the branch with which it was connected also disappears. It is guaranteed that no other apple is hanging from the apple that Vanellope will pick.

Let's call a word a sequence of letters on branches going from the root to the apple. A subword is a non-empty number of consecutive letters in a word.

You need to count the number of different subwords after each action. Subwords are considered different if there are positions that contain different letters.

Input

The first line contains the number of actions q (1 ≤ q ≤ 100000). Each of the following q lines contains a description of the action in the following format:

• 1 p c (1 ≤ p ≤ n) means that Ralph adds an apple with the minimum positive number that has not yet been used. The ancestor of the new apple is the apple v, and the Latin letter c is written on the branch.
• 2 v means that Vanellope picks an apple with number v. It is guaranteed that the root apple will not be picked, and no apple will be picked twice.

Output

After each action print the number of distinct subwords.

Note

After the first operation there is a word "a". Various subwords: "a".

After the second operation, the words are "a", "b". Various subwords: "a", "b".

After the third operation, the words are "a", "b", "a". Various subwords: "a", "b".

After the fourth operation, the words are "a", "b", "ac". Various subwords: "a", "b", "ac", "c".

After the fifth operation, the words are "a", "ac". Various subwords: "a", "ac", "c".