Trò chơi với hai cây

Ta xét hai cây có gốc. Ban đầu mỗi cây chỉ gồm đúng một đỉnh mang số hiệu $1$, chính là gốc của cây đó. Mỗi cạnh của cây được gắn một chữ cái Latin thường.

Với một cây, dãy đỉnh $v_1,v_2,\dots ,v_k$ ($k\ge 1$) được gọi là đường đi xuôi nếu với mọi $i$ từ $1$ đến $k-1$, đỉnh $v_i$ là cha trực tiếp của đỉnh $v_{i+1}$. Viết lần lượt các chữ cái trên các cạnh của đường đi này theo thứ tự từ $v_1$ đến $v_k$, ta được một xâu tương ứng với đường đi xuôi đó (khi $k=1$ xâu này rỗng).

Tương tự, dãy đỉnh $v_1,v_2,\dots ,v_k$ ($k\ge 1$) được gọi là đường đi ngược nếu với mọi $i$ từ $1$ đến $k-1$, đỉnh $v_i$ là con trực tiếp của đỉnh $v_{i+1}$. Xâu tương ứng cũng được viết theo thứ tự từ $v_1$ đến $v_k$ (khi $k=1$ xâu này rỗng).

Cho $n$ thao tác, mỗi thao tác gồm ba giá trị $(t,v,c)$:

• $t$ là chỉ số cây được thao tác ($1$ hoặc $2$);
• $v$ là số hiệu một đỉnh đang có trong cây đó;
• $c$ là một chữ cái Latin thường.

Thao tác này thêm vào cây $t$ một đỉnh mới mang số hiệu $m+1$, trong đó $m$ là số đỉnh hiện tại của cây $t$, và nối đỉnh $v$ với đỉnh mới bằng một cạnh mang chữ cái $c$. Như vậy đỉnh mới là con trực tiếp của $v$.

Bộ ba số nguyên có thứ tự $(i,j,q)$ được gọi là một bộ ba đẹp nếu:

• $1\le i\le m_1$, với $m_1$ là số đỉnh hiện tại của cây thứ nhất;
• $1\le j,q\le m_2$, với $m_2$ là số đỉnh hiện tại của cây thứ hai;
• trong cây thứ hai tồn tại đường đi xuôi $v_1,v_2,\dots ,v_k$ với $v_1=j$ và $v_k=q$;
• xâu tương ứng với đường đi xuôi từ $j$ đến $q$ trong cây thứ hai bằng đúng xâu tương ứng với đường đi ngược từ đỉnh $i$ về đỉnh $1$ trong cây thứ nhất.

Cả hai đường đi nói trên, nếu tồn tại, đều là duy nhất. Lưu ý rằng $j=q$ được chấp nhận và khi đó xâu tương ứng là xâu rỗng.

Hãy tính số bộ ba đẹp sau mỗi thao tác.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số thao tác.
• $n$ dòng tiếp theo, mỗi dòng chứa một thao tác dưới dạng t v c, theo đúng thứ tự thực hiện.

Dữ liệu ra

In ra đúng $n$ dòng, dòng thứ $x$ chứa một số nguyên là số bộ ba đẹp sau khi thực hiện thao tác thứ $x$.

Ràng buộc

• $1\le n\le 700$
• $t\in \{1,2\}$
• $1\le v\le$ số đỉnh hiện tại của cây $t$
• $c$ là chữ cái Latin thường

Ví dụ