2101. 拨打电话 / Dialing
用一棵有根树 T 表示简化的电话网络。在 T 中，每个叶结点对应一个具体的通话终端，而每个内部结点表示可以处理通话请求的交换节点。每个通话终端都有一个自己的号码 a_i，但是为了让交换节点正确处理通话请求，通常需要在原始号码的前面加上若干前缀编号，用于指明被呼叫者在电话网络中所处的位置。例如，从中国大陆的其它地区拨打北京市的固定电话，则需要在前面按顺序加上长途冠码 0 及北京市区号 10，才能正确地拨通对应的电话。在 T 中，从通话终端 u 向通话终端 v 拨打电话时，正确的电话号码应通过沿着在 T 上从 u 到 v 的最短路，按顺序连接各交换节点相应前缀号（即最靠近 u 的交换节点的前缀号应在最前，最靠近 v 的交换节点的前缀号应在最后）后，加上 v 本身的号码得到。
在 T 中，根据发出请求的通话终端、接受请求的通话终端与交换节点的关系，每个交换节点各有 3 种可能为空的前缀号，分别为：
从该交换节点 v 在 T 中对应子树内向子树外拨打电话时需要加的前缀号 b_v，如从中国大陆拨打其它国家或地区的电话时需加国际冠码
00；从该交换节点 v 在 T 中对应子树外向子树内拨打电话时需要加的前缀号 c_v，如从其它国家或地区向中国大陆拨打电话时需加中国大陆的国际区码
86；从该交换节点 v 在 T 中任意一子结点（子结点可能为某一通话终端，也可能是其它交换节点，后同）向 v 发出请求，v 需要将该请求转发给另外一子结点进行处理时的需要加的前缀号 d_v，如从中国大陆的其它地区拨打北京市的固定电话
ABCDEFGH，需要使用长途冠码0，对应电话号码为010-ABCDEFGH；而从其它国家或地区拨打北京市的同一电话，则只需在国际冠码之后拨打86-10-ABCDEFGH，不需要使用长途冠码0。
现在给出 T 中若干个通话请求，每个请求由拨出结点和该请求在该结点拨打的电话号码组成，请判断拨打的电话号码是否对应唯一的通话终端。如果是，请求出该通话终端；否则，请求出与该电话号码对应的通话终端数量。
输入
输入的第一行包含两个正整数 n, q，表示电话网络 T 的结点数和通话请求的数量。保证 2\le n\le 10^5，1\le q\le 10^5。
接下来 n 行，每行输入两个非负整数和一个字符串 f_i，t_i，s_i，分别由一个空格隔开，描述 T 的第 i 个结点。其中，f_i>0 时表示结点 i 在 T 上的父结点编号，f_i=0 表示结点 i 是 T 的根；t_i\in{0,1} 表示结点 i 是否为叶结点，
如果 t_i=1，则结点 i 为叶结点，此时 s_i 是仅由字符
0至9构成的非空字符串，表示结点 i 的原始电话号码 a_i；如果 t_i = 0，则结点 i 为内部交换节点，此时 s_i 包含三个由单个
/字符隔开的仅由字符0至9构成的字符串（可能为空），分别为前缀号 b_i，c_i 和 d_i。
保证 0\le f_i < i，所有叶结点的 a_i 及所有内部 b_i, c_i, d_i 的总长不超过 3\times 10^6。
接下来 q 行，每行输入一个正整数 p_i 和一个仅包含字符 0 至 9 的非空字符串 r_i，表示在结点 p_i 拨打电话号码为 r_i 的通话请求。保证 p_i 对应叶结点，\sum_{i=1}^q \left|r_i\right| \le 3\times10^6。
输出
对每个通话请求输出一行。如果拨打的电话号码对应唯一的通话终端，输出 1 x，其中正整数 x 是该通话终端的编号；否则，输出 0 y，其中非负整数 y 是匹配的通话终端的数量。
样例
| 标准输入 复制文本 |
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 |
| 标准输出 复制文本 |
1 4 0 0 0 0 1 5 1 11 1 13 1 18 1 21 1 22 1 24 |
| 标准输入 复制文本 |
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 |
| 标准输出 复制文本 |
0 0 1 3 0 2 0 0 0 2 1 4 |
| 标准输入 复制文本 |
103 104 0 0 //0 1 0 /138/ 2 0 /22/22 3 1 0306 3 1 1001 2 0 /23/23 6 1 5440 6 1 6288 1 0 /3/ 9 0 /3254/3254 10 1 0753 9 0 /5530/5530 12 1 1111 9 0 /5876/5876 14 1 5835 9 0 /5962/5962 16 1 4481 9 0 /6450/6450 18 1 5703 1 0 /4992/ 20 0 /8/8 21 1 0321 21 1 1242 1 0 /55/ 24 0 /929/929 25 1 8633 24 0 /932/932 27 1 7879 24 0 /933/933 29 1 1900 29 1 7008 24 0 /934/934 32 1 2800 32 1 4747 24 0 /941/941 35 1 3126 35 1 3341 35 1 3448 24 0 /943/943 39 1 2104 39 1 2121 39 1 2136 39 1 2331 24 0 /949/949 44 1 5840 24 0 /952/952 46 1 1122 46 1 2411 24 0 /962/962 49 1 0653 49 1 1384 49 1 1650 49 1 3225 24 0 /963/963 54 1 3200 54 1 5875 24 0 /977/977 57 1 1201 1 0 /558/ 59 0 /72/72 60 1 7111 59 0 /94/94 62 1 5151 1 0 /76/ 64 0 /220/220 65 1 2356 64 0 /221/221 67 1 2646 64 0 /223/223 69 1 8555 69 1 9565 64 0 /224/224 72 1 5511 64 0 /231/231 74 1 1462 64 0 /232/232 76 1 3066 76 1 5555 76 1 6200 64 0 /234/234 80 1 3800 64 0 /245/245 82 1 6450 64 0 /247/247 84 1 8999 64 0 /254/254 86 1 5020 86 1 5081 64 0 /256/256 89 1 5642 64 0 /261/261 91 1 1717 64 0 /262/262 93 1 7605 1 0 /761/ 95 0 /22/22 96 1 0120 95 0 /58/58 98 1 1805 95 0 /73/73 100 1 5300 95 0 /77/7 102 1 1234 4 0559298633 5 0762212646 7 0559344747 8 0559771201 11 0762343800 13 0559633200 15 0762311462 17 0559337008 19 0761771234 22 0355301111 23 0762611717 26 0138236288 28 9432104 30 9522411 31 0762545020 33 0499281242 34 9621384 36 9495840 37 0762456450 38 0558945151 40 0499280321 41 0358765835 42 9623225 43 0558727111 45 9413448 47 0332540753 48 9331900 50 0762627605 51 0762478999 52 0762326200 53 0762565642 55 0138235440 56 9521122 58 0359624481 61 0559635875 63 0559621650 66 0138220306 68 0138221001 70 0761220120 71 0761581805 73 2238555 75 0559432121 77 0559432136 78 2245511 79 0364505703 81 2325555 83 2239565 85 2323066 87 0559432331 88 0559342800 90 0559413126 92 2202356 94 0559327879 97 0559413341 99 735300 101 0762545081 103 0559620653 22 81242 83 0559432104 37 0762239565 73 0358765835 34 0762478999 58 0558727111 99 0559337008 47 0138235440 56 0762545081 47 0761771234 73 2611717 97 0332540753 58 0762326200 48 9999999999 23 0332540753 23 0762326200 78 2565642 45 0762212646 63 0559413126 34 0762627605 58 0762611717 101 0559413448 34 0762323066 101 0762202356 63 00559495840 28 0358765835 75 2323066 28 9298633 63 0499281242 66 0499281242 83 0559413126 101 0559298633 85 0499281242 15 0762212646 101 0499280321 70 0559635875 53 9413126 103 0138220306 88 2611717000 45 0762545081 94 0559344747 63 0762325555 38 0364505703 101 0762245511 36 0762239565 48 0499281242 88 0559413341 |
| 标准输出 复制文本 |
1 26 1 68 1 34 1 58 1 81 1 55 1 75 1 31 1 103 1 13 1 92 1 8 1 40 1 48 1 87 1 23 1 51 1 45 1 83 1 63 1 22 1 15 1 53 1 61 1 38 1 11 1 30 1 94 1 85 1 79 1 90 1 7 1 47 1 17 1 56 1 52 1 4 1 5 1 97 1 99 1 70 1 41 1 42 1 73 1 19 1 78 1 71 1 77 1 43 1 33 1 36 1 66 1 28 1 37 1 101 1 88 1 50 1 23 1 40 1 71 1 15 1 85 1 61 1 31 1 7 1 88 1 103 1 92 1 11 1 79 0 0 1 11 1 79 1 90 1 68 1 36 1 94 1 92 1 38 1 77 1 66 0 0 1 15 1 77 1 26 1 23 1 23 1 36 1 26 1 23 1 68 1 22 1 56 1 36 1 4 0 0 1 88 1 34 1 78 1 19 1 73 1 71 1 23 1 37 |
提示
为方便理解题意，该样例使用了实际存在的电话号码。其表示的电话网络见下图。
第一个询问的通话请求是从北京大学计算机学院至清华大学后勤综合服务热线/校内查号台。因为这两个结点的父结点均为结点 3（对应北京市），且父结点 d_3=\varepsilon，所以直接拨打对应电话即可。第二个询问为第一个询问加上区号的版本，在本题中认为该询问的电话号码无法拨通。
第四个询问为香港科技大学（广州）向清华大学招生办公室发出通话请求。由于两个通话终端的父结点不同，拨打电话时应加上前缀 b_9 + d_2 + c_3=
010。第三个询问与第四个询问类似，但是没有加上前缀，故无法拨通。第五个询问为中国计算机学会致电广东省计算机学会，计算应拨打电话号码的方式为 b_3 + d_2 + c_9 + a_{11}。
第六个询问为从香港科技大学（广州）向香港科技大学计算机科学与工程系（Department of Computer Science and Engineering）发出通话请求。拨打电话时，应先按顺序拨打中国大陆的国际冠码 b_2=
00和中国香港的国际区码 c_{12}=852，然后再键入原始电话号码 a_{13}（完整的计算方法为 b_9 + b_2 + d_1 + c_{12} + a_{13}）。第七个询问为从东京大学研究生院计算机科学专业办公室拨至情报理工学系研究科招生办公室。由于本乡校区的内部电话需要在 4 位电话之前加上 d_{16}=
2，正确的电话号码为2+7926=27926。第八个询问为东京大学研究生院计算机科学专业办公室向大阪大学研究生院信息科学研究科办公室拨打电话。拨打电话时，应先后加上长途冠码 d_{14}=
0、大阪的区号（市外局番）c_{19}=6和吹田校区所属的子区域区号（市内局番）c_{20}=6879。应拨打的电话号码的完整表达式为 b_{16}+b_{15}+d_{14}+c_{19}+c_{20}+a_{21}。第九个询问为从大阪大学研究生院信息科学研究科办公室拨打电话给同样位于吹田校区的生命机能研究科。d_{20}=\varepsilon 意味着吹田校区的内部电话不需要加前缀，可以直接拨打对应 4 位电话号码。
第十个询问为从大阪大学研究生院信息科学研究科办公室向大阪大学信息科学系的办公室拨打电话。由于本科的信息科学系位于丰中校区，所以需要在原始电话号码前加上丰中校区对应的子区域区号（市内局番）c_{23}=
6850（实际拨打电话时，也可以使用丰中校区的内部电话前缀172，但这不在本题考虑范围之内）。
从结点 2 的子树中拨打 0100，可以匹配到结点 3 和结点 5；拨打 0101，可以匹配到结点 4 和结点 6。因为一个结点播出的电话号码不能匹配自己，所以只有第二个询问和第六个询问拨出的电话号码对应唯一的通话终端。