A rooted tree $T$ represents a simplified telephone network. In $T$, each leaf node corresponds to a specific communication terminal, and each internal node represents a switching node capable of processing call requests. Each terminal has its own number $a_i$, but to ensure the switching nodes correctly process a call, it is usually necessary to prepend several prefix codes to the original number to indicate the caller's and callee's locations within the network. For example, when calling a landline in Beijing from other parts of mainland China, one must prepend the long-distance prefix 0 and the Beijing area code 10 to the number to connect correctly. In $T$, when a call is made from terminal $u$ to terminal $v$, the correct phone number is obtained by concatenating the prefix codes of the switching nodes along the shortest path from $u$ to $v$ in $T$ (the prefix of the switching node closest to $u$ comes first, and the prefix of the switching node closest to $v$ comes last), followed by the number $a_v$ of terminal $v$.

In $T$, depending on the relationship between the requesting terminal, the receiving terminal, and the switching node, each switching node has $3$ types of prefix codes (which may be empty):

• $b_v$: The prefix code required when a call is made from within the subtree of switching node $v$ to outside the subtree, such as the international access code 00 when calling abroad from mainland China.
• $c_v$: The prefix code required when a call is made from outside the subtree of switching node $v$ to inside the subtree, such as the country code 86 when calling mainland China from abroad.
• $d_v$: The prefix code required when a request is forwarded by $v$ from one child node to another child node (a child node may be a terminal or another switching node). For example, calling a Beijing landline ABCDEFGH from other parts of mainland China requires the long-distance prefix 0, resulting in 010-ABCDEFGH; calling the same number from abroad only requires the international access code followed by 86-10-ABCDEFGH, without the long-distance prefix 0.

Given several call requests in $T$, each consisting of the originating node and the dialed phone number, determine whether the phone number corresponds to a unique terminal. If it does, output the ID of that terminal; otherwise, output the number of terminals matching that phone number.

Input

The first line contains two positive integers $n$ and $q$, representing the number of nodes in the telephone network $T$ and the number of call requests. It is guaranteed that $2 \le n \le 10^5$ and $1 \le q \le 10^5$.

The next $n$ lines each contain two non-negative integers and a string $f_i, t_i, s_i$, separated by spaces, describing the $i$-th node of $T$. If $f_i > 0$, it represents the parent node ID of node $i$; if $f_i = 0$, node $i$ is the root of $T$. $t_i \in \{0, 1\}$ indicates whether node $i$ is a leaf node:

• If $t_i = 1$, node $i$ is a leaf node, and $s_i$ is a non-empty string consisting only of characters 0 to 9, representing the original phone number $a_i$ of node $i$.
• If $t_i = 0$, node $i$ is an internal switching node, and $s_i$ contains three strings (possibly empty) consisting only of characters 0 to 9, separated by single / characters, representing the prefix codes $b_i, c_i,$ and $d_i$ respectively.

It is guaranteed that $0 \le f_i < i$, and the total length of all $a_i$ for leaf nodes and all $b_i, c_i, d_i$ for internal nodes does not exceed $3 \times 10^6$.

The next $q$ lines each contain a positive integer $p_i$ and a non-empty string $r_i$ consisting only of characters 0 to 9, representing a call request from node $p_i$ with the phone number $r_i$. It is guaranteed that $p_i$ corresponds to a leaf node, and $\sum_{i=1}^q |r_i| \le 3 \times 10^6$.

Output

For each call request, output one line. If the dialed phone number corresponds to a unique terminal, output 1 x, where $x$ is the ID of that terminal. Otherwise, output 0 y, where $y$ is the number of matching terminals.

Examples

Input 1

24 10
0 0 //
1 0 00/86/0
2 0 /10/
3 1 62793001
3 1 62770334
3 1 62783054
3 1 62757487
3 1 62562503
2 0 /20/
9 1 88331234
9 1 83561784
1 0 001/852/
12 1 23587000
1 0 010/81/0
14 0 /3/
15 0 /5841/2
16 1 4111
16 1 7926
14 0 /6/
19 0 /6879/
20 1 4508
20 1 4421
19 0 /6850/
23 1 6618
7 62793001
7 01062793001
10 62770334
10 01062770334
8 02083561784
10 0085223587000
17 27926
17 0668794508
21 4421
21 68506618

Output 1

1 4
0 0
0 0
1 5
1 11
1 13
1 18
1 21
1 22
1 24

Note 1

• The first request is from the School of Computer Science at Peking University to the Tsinghua University logistics service hotline/internal directory assistance. Since both nodes share the same parent node $3$ (Beijing) and $d_3 = \varepsilon$, the number is dialed directly. The second request is the version with the area code added; in this problem, it is considered unreachable.
• The fourth request is from the Hong Kong University of Science and Technology (Guangzhou) to the Tsinghua University Admissions Office. Since the two terminals have different parents, the prefix $b_9 + d_2 + c_3 = $ 010 should be added. The third request is similar but lacks the prefix, so it is unreachable.
• The fifth request is from the China Computer Federation to the Guangdong Computer Federation; the number is calculated as $b_3 + d_2 + c_9 + a_{11}$.
• The sixth request is from the Hong Kong University of Science and Technology (Guangzhou) to the Department of Computer Science and Engineering at the Hong Kong University of Science and Technology. The call should include the international access code $b_2 = $ 00 and the Hong Kong area code $c_{12} = $ 852, followed by $a_{13}$ (full calculation: $b_9 + b_2 + d_1 + c_{12} + a_{13}$).
• The seventh request is from the University of Tokyo Graduate School of Science, Department of Computer Science office to the Graduate School of Information Science and Technology admissions office. Since the Hongo campus internal phone requires $d_{16} = $ 2 before the 4-digit number, the correct number is 2 + 7926 = 27926.
• The eighth request is from the University of Tokyo Graduate School of Science, Department of Computer Science office to the Osaka University Graduate School of Information Science and Technology office. The call should include the long-distance prefix $d_{14} = $ 0, the Osaka area code $c_{19} = $ 6, and the Suita campus sub-area code $c_{20} = $ 6879. The full expression is $b_{16} + b_{15} + d_{14} + c_{19} + c_{20} + a_{21}$.
• The ninth request is from the Osaka University Graduate School of Information Science and Technology office to the Graduate School of Frontier Biosciences, also located on the Suita campus. $d_{20} = \varepsilon$ means no prefix is needed for internal Suita campus calls.
• The tenth request is from the Osaka University Graduate School of Information Science and Technology office to the Osaka University Department of Information Science office. Since the undergraduate Department of Information Science is located on the Toyonaka campus, the Toyonaka sub-area code $c_{23} = $ 6850 must be added.

Input 2

6 6
0 0 0/0/1
1 0 0/1/01
1 1 00
1 1 01
2 1 00
2 1 01
5 00
5 0100
5 0101
6 01
6 0100
6 0101

Output 2

0 0
1 3
0 2
0 0
0 2
1 4

Note 2

Dialing 0100 from the subtree of node $2$ matches nodes $3$ and $5$; dialing 0101 matches nodes $4$ and $6$. Since a call cannot match the originating terminal, only the second and sixth requests correspond to a unique terminal.

Note 3

See ex_3.in and ex_3.ans in the download directory.