Let us imagine a tree of stacks such that each stack from the task corresponds to a path to a certain node in the tree from the root of the tree. Each node will have an integer ~x~ assigned to it, excluding the root, which will be assigned zero. Every stack label ~v~ will then have a tree node assigned to it, call it ~f_v~. Precisely the number of the node ~f_v~ is the number from the top of stack ~v~, and climbing up to the root we would see the whole stack. All the while ignoring the zero at the root, of course.

Let us make sure that this is really possible. At the beginning of the game, we have one empty stack and make a tree with the node zero. While copying stack ~v~ and adding a new number we simply add a new node to the tree, assign a number to it and set ~f_v~ as its parent. While copying stack ~v~ and removing an element from its top, we will output the number in node ~f_v~ and assign the parent of ~f_v~ to the new stack. It is evident that the tree-like structure is stable after each operation and that all operations are of constant complexity.

We are still left with efficiently answering the query of type c. For starters, let us notice that the numbers placed on stacks are always ascending. In other words, no two tree nodes will have the same number ~x~ written in them. So the question "how many of the same numbers are in stacks ~v~ and ~w~" is equal to the question "how many of the same nodes, excluding the root, is on the path from the root to ~f_v~ and on the path from the root to ~f_w~". All such nodes will be in the first part of the path from the root to ~f_v/f_w~ because once the paths part ways, they will never meet again. Therefore, it is sufficient to find the last such node and output how many nodes there are on the path from the root to itself.

Such node is also called the lowest common ancestor in a tree and there are various methods to find it. The most popular solution is "jumps of powers of 2 length" (for more information, consult this link, of the complexity ~\mathcal O(N \log N)~ for preprocessing and ~\mathcal O(\log N)~ per query.

Additionally, we need to notice that in this task we don't have a complete tree for which we can initially build a jumping table, but it isn't a problem. When adding a new node (the only moment when the tree changes), we will calculate all its jumps in the complexity ~\mathcal O(\log N)~ because the jumps of its ancestors have already been calculated.

The total time and memory complexity of this solution is ~\mathcal O(N \log N)~.