11176: NOI2024 - D2T2 登山
[Creator : ]
Description
“为什么要攀登？因为山就在那里。”
慕士塔格山上有 $n$ 处点位，点从 $1$ 到 $n$ 编号，$1$ 号点位为山顶。这 $n$ 个点位构成一棵有根树的结构，其中 $1$ 号点位为根，对于 $2\leq i\leq n$，$i$ 号点位的父亲结点为 $p_i$ 号点位。
记 $d_i$ 为 $i$ 号点位到山顶所需经过的边数。形式化地说，$d_1=0$，对于 $2\leq i\leq n$，$d_i=d_{p_i}+1$。
定义一条**登山路径**为从 $2\sim n$ 号点位中的某一个开始，经过若干次**移动**后**到达山顶**的方案。
定义一次从 $i(2\leq i\leq n)$ 号点位出发的**移动**为以下两种方式之一：
1. 冲刺：在给定的冲刺范围 $[l_i,r_i]$ 内，选择一个正整数 $k$ 满足 $l_i\leq k\leq r_i$，向山顶移动 $k$ 步，即移动至 $i$ 号点位在有根树上的 $k$ 级父亲处。保证 $1\leq l_i\leq r_i\leq d_i$。
2. 休息：由于慕士塔格山地形陡峭，休息时会滑落到某一个儿子结点处。形式化地说，选择一个满足 $p_j=i$ 的 $j$，移动至到 $j$ 号点位。特别地，若 $i$ 号点位为有根树的叶子结点，则不存在满足 $p_j=i$ 的 $j$，因此此时不能选择休息。
定义一条**登山路径**对应的**登山序列**为初始点位以及每次移动到的点位所构成的序列。形式化地说，一条从 $x$ 号点位开始的**登山路径**对应的****登山序列****是一个点序列 $a_1=x,a_2,\dots,a_m=1$ 满足对于 $1\leq i<m$，$a_{i+1}$ 是 $a_i$ 的 $k(l_{a_i}\leq k\leq r_{a_i})$ 级祖先或 $p_{a_{i+1}}=a_i$。
为了保证每次冲刺都能更接近山顶，一条**合法的登山路径**需要满足：对于初始点位或某次移动到的点位 $i$，以后冲刺到的点位 $j$ 都必须满足 $d_j<d_i-h_i$，其中 $h_i$ 是一个给定的参数，保证 $0\leq h_i<d_i$。形式化地说，一条**合法的登山路径**对应的**登山序列** $a_1,a_2,\dots,a_m$ 需要满足：对于所有 $1\leq i<j\leq m$，若 $p_{a_j} \neq a_{j-1}$，则 $d_{a_j}<d_{a_i}-h_{a_i}$。
对于 $2\sim n$ 号所有点位，求从这些点位开始的**合法的登山路径**条数。两条**登山路径**不同当且仅当其对应的**登山序列**不同。由于答案可能较大，你只需要求出答案对 $998\,244\,353$ 取模后的结果。
慕士塔格山上有 $n$ 处点位，点从 $1$ 到 $n$ 编号，$1$ 号点位为山顶。这 $n$ 个点位构成一棵有根树的结构，其中 $1$ 号点位为根，对于 $2\leq i\leq n$，$i$ 号点位的父亲结点为 $p_i$ 号点位。
记 $d_i$ 为 $i$ 号点位到山顶所需经过的边数。形式化地说，$d_1=0$，对于 $2\leq i\leq n$，$d_i=d_{p_i}+1$。
定义一条**登山路径**为从 $2\sim n$ 号点位中的某一个开始，经过若干次**移动**后**到达山顶**的方案。
定义一次从 $i(2\leq i\leq n)$ 号点位出发的**移动**为以下两种方式之一：
1. 冲刺：在给定的冲刺范围 $[l_i,r_i]$ 内，选择一个正整数 $k$ 满足 $l_i\leq k\leq r_i$，向山顶移动 $k$ 步，即移动至 $i$ 号点位在有根树上的 $k$ 级父亲处。保证 $1\leq l_i\leq r_i\leq d_i$。
2. 休息：由于慕士塔格山地形陡峭，休息时会滑落到某一个儿子结点处。形式化地说，选择一个满足 $p_j=i$ 的 $j$，移动至到 $j$ 号点位。特别地，若 $i$ 号点位为有根树的叶子结点，则不存在满足 $p_j=i$ 的 $j$，因此此时不能选择休息。
定义一条**登山路径**对应的**登山序列**为初始点位以及每次移动到的点位所构成的序列。形式化地说，一条从 $x$ 号点位开始的**登山路径**对应的****登山序列****是一个点序列 $a_1=x,a_2,\dots,a_m=1$ 满足对于 $1\leq i<m$，$a_{i+1}$ 是 $a_i$ 的 $k(l_{a_i}\leq k\leq r_{a_i})$ 级祖先或 $p_{a_{i+1}}=a_i$。
为了保证每次冲刺都能更接近山顶，一条**合法的登山路径**需要满足：对于初始点位或某次移动到的点位 $i$，以后冲刺到的点位 $j$ 都必须满足 $d_j<d_i-h_i$，其中 $h_i$ 是一个给定的参数，保证 $0\leq h_i<d_i$。形式化地说，一条**合法的登山路径**对应的**登山序列** $a_1,a_2,\dots,a_m$ 需要满足：对于所有 $1\leq i<j\leq m$，若 $p_{a_j} \neq a_{j-1}$，则 $d_{a_j}<d_{a_i}-h_{a_i}$。
对于 $2\sim n$ 号所有点位，求从这些点位开始的**合法的登山路径**条数。两条**登山路径**不同当且仅当其对应的**登山序列**不同。由于答案可能较大，你只需要求出答案对 $998\,244\,353$ 取模后的结果。
Input
**本题有多组测试数据。**
输入的第一行包含一个整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。
输入的第二行包含一个整数 $t$，表示测试数据组数。
接下来依次输入每组测试数据，对于每组测试数据：
输入的第一行包含一个整数 $n$，表示慕士塔格山的点位数量。
接下来 $n-1$ 行，第 $i-1(2\leq i\leq n)$ 行包含四个整数 $p_i,l_i,r_i,h_i$。保证 $1\leq p_i<i$，$1\leq l_i\leq r_i\leq d_i$，$0\leq h_i<d_i$。
输入的第一行包含一个整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。
输入的第二行包含一个整数 $t$，表示测试数据组数。
接下来依次输入每组测试数据，对于每组测试数据：
输入的第一行包含一个整数 $n$，表示慕士塔格山的点位数量。
接下来 $n-1$ 行，第 $i-1(2\leq i\leq n)$ 行包含四个整数 $p_i,l_i,r_i,h_i$。保证 $1\leq p_i<i$，$1\leq l_i\leq r_i\leq d_i$，$0\leq h_i<d_i$。
Output
对于每组测试数据，输出一行 $n-1$ 个整数，分别表示从点位 $2\sim n$ 到达山顶的方案数对 $998\,244\,353$ 取模后的结果。
Constraints
对于所有测试数据保证：$1\leq t\leq 4$，$2\leq n\leq 10^5$。
对于任意的 $2\leq i\leq n$，保证：$1\leq p_i<i$，$1\leq l_i\leq r_i\leq d_i$，$0\leq h_i<d_i$。
对于任意的 $2\leq i\leq n$，保证：$1\leq p_i<i$，$1\leq l_i\leq r_i\leq d_i$，$0\leq h_i<d_i$。
Sample 1 Input
0
3
5
1 1 1 0
2 1 1 0
2 1 2 1
4 2 3 0
6
1 1 1 0
2 1 2 0
3 1 3 2
4 1 4 1
5 1 5 3
6
1 1 1 0
2 1 2 0
2 1 2 0
3 1 2 0
3 2 3 2
Sample 1 Output
3 3 2 4
5 9 3 21 6
4 10 5 14 1
样例 $1$ 共包含三组测试数据。
对于第一组测试数据，慕士塔格山的点位结构如下：
在该测试数据中，$d_1=0$，$d_2=1$，$d_3=d_4=2$，$d_5=3$。
从 $4$ 开始的合法的登山路径共有以下 $2$ 条：
1. 直接选择冲刺到 $4$ 的 $2$ 级父亲，也就是 $1$，到达山顶，对应的登山序列为 $[4,1]$。
2. 先休息滑落到 $5$，然后从 $5$ 冲刺到它的 $3$ 级父亲，到达山顶。对应的登山序列为 $[4,5,1]$。
从 $5$ 开始的合法的登山路径共有以下 $4$ 条：
1. 直接选择冲刺到 $5$ 的 $3$ 级父亲，也就是 $1$，到达山顶。对应的登山序列为 $[5,1]$。
2. 先冲刺到 $5$ 的 $2$ 级父亲，也就是 $2$；然后再从 $2$ 冲刺到它的 $1$ 级父亲，到达山顶。对应的登山序列为 $[5,2,1]$。
3. 先冲刺到 $5$ 的 $2$ 级父亲，也就是 $2$；然后在 $2$ 处休息，滑落到 $4$；接着从 $4$ 冲刺到它的 $2$ 级父亲，到达山顶。对应的登山序列为 $[5,2,4,1]$。
4. 先冲刺到 $5$ 的 $2$ 级父亲，也就是 $2$；然后在 $2$ 处休息，滑落到 $4$；继续休息，滑落到 $5$；接着从 $5$ 再次冲刺到它的 $3$ 级父亲，到达山顶。对应的登山序列为 $[5,2,4,5,1]$。
对于第一组测试数据，慕士塔格山的点位结构如下：
在该测试数据中，$d_1=0$，$d_2=1$，$d_3=d_4=2$，$d_5=3$。
从 $4$ 开始的合法的登山路径共有以下 $2$ 条：
1. 直接选择冲刺到 $4$ 的 $2$ 级父亲，也就是 $1$，到达山顶，对应的登山序列为 $[4,1]$。
2. 先休息滑落到 $5$，然后从 $5$ 冲刺到它的 $3$ 级父亲，到达山顶。对应的登山序列为 $[4,5,1]$。
从 $5$ 开始的合法的登山路径共有以下 $4$ 条：
1. 直接选择冲刺到 $5$ 的 $3$ 级父亲，也就是 $1$，到达山顶。对应的登山序列为 $[5,1]$。
2. 先冲刺到 $5$ 的 $2$ 级父亲，也就是 $2$；然后再从 $2$ 冲刺到它的 $1$ 级父亲，到达山顶。对应的登山序列为 $[5,2,1]$。
3. 先冲刺到 $5$ 的 $2$ 级父亲，也就是 $2$；然后在 $2$ 处休息，滑落到 $4$；接着从 $4$ 冲刺到它的 $2$ 级父亲，到达山顶。对应的登山序列为 $[5,2,4,1]$。
4. 先冲刺到 $5$ 的 $2$ 级父亲，也就是 $2$；然后在 $2$ 处休息，滑落到 $4$；继续休息，滑落到 $5$；接着从 $5$ 再次冲刺到它的 $3$ 级父亲，到达山顶。对应的登山序列为 $[5,2,4,5,1]$。
Sample 2 Input
0
4
300
1 1 1 0
1 1 1 0
2 2 2 0
3 1 2 1
5 1 2 1
3 1 2 0
7 1 1 1
7 1 3 1
7 3 3 0
7 2 3 1
11 1 4 3
10 2 4 0
13 1 3 2
13 1 3 0
15 4 4 4
13 4 5 4
15 1 2 3
18 2 7 2
17 4 6 0
17 1 3 3
20 3 7 1
21 4 7 0
22 1 5 2
22 8 8 5
24 7 8 6
25 4 6 5
25 1 3 4
28 9 9 7
26 9 9 1
29 9 11 7
30 7 10 1
32 12 12 10
31 8 11 6
31 8 10 8
32 6 8 3
36 7 11 11
36 1 5 2
37 1 4 5
39 3 12 4
39 1 5 5
40 2 6 14
39 11 12 3
43 10 12 10
42 12 17 4
43 6 16 14
43 2 11 5
47 15 15 8
46 1 16 10
49 7 9 7
47 10 17 14
51 7 9 5
51 2 10 10
53 4 14 18
54 1 10 10
54 6 18 13
55 10 11 7
55 6 6 6
56 2 6 14
57 17 22 10
57 14 19 10
58 16 19 18
62 9 11 16
62 3 21 5
62 1 4 21
62 1 21 3
63 7 8 9
66 5 10 7
67 12 19 24
68 6 24 11
69 4 26 12
68 17 17 7
69 9 17 0
72 3 15 24
72 6 19 1
75 2 14 16
76 19 28 10
74 1 27 20
78 11 24 19
79 9 21 11
77 9 17 16
78 7 14 10
82 2 11 20
81 7 21 9
84 6 10 30
83 8 21 4
86 3 15 13
87 1 15 7
86 6 14 19
89 31 32 18
89 24 26 25
89 2 18 31
92 20 32 10
91 21 28 14
93 2 11 12
95 18 35 18
94 4 18 20
94 4 8 29
97 6 12 11
96 7 10 18
97 16 31 27
99 14 21 18
100 11 13 17
100 27 34 33
102 23 33 19
105 8 33 22
104 18 24 26
107 10 30 28
105 13 31 1
109 16 35 15
109 6 20 2
108 34 35 35
110 4 38 34
112 12 15 24
112 6 6 6
115 9 21 30
115 21 26 0
117 30 32 42
116 14 38 11
116 21 28 42
120 10 36 13
120 25 39 39
120 10 30 6
121 25 28 8
122 24 24 36
124 8 17 27
126 7 46 35
124 6 32 4
125 7 10 44
126 30 38 2
130 42 45 0
130 6 28 35
129 13 20 6
131 30 39 43
133 17 17 42
133 37 45 41
133 8 24 37
134 4 28 20
138 28 38 19
136 21 28 0
139 25 30 44
140 24 38 9
141 9 51 1
141 1 33 49
142 30 39 29
143 4 51 3
143 1 4 26
146 3 22 6
148 41 52 41
147 31 42 40
148 5 10 55
149 29 34 14
152 31 32 17
152 9 47 13
153 46 55 27
154 19 29 16
154 26 30 56
157 17 49 12
158 36 57 53
157 36 45 1
157 34 57 28
158 1 43 21
160 27 28 23
161 8 39 53
164 12 47 26
164 14 26 51
164 18 55 16
166 51 54 44
166 32 57 12
168 16 40 2
167 7 32 3
168 17 60 56
172 13 61 29
172 22 59 48
172 9 60 21
175 14 53 61
175 20 53 36
177 3 10 19
177 17 60 57
177 10 27 27
180 16 19 43
178 1 14 60
182 19 26 3
182 19 20 9
182 10 10 20
183 36 37 62
184 40 67 22
187 32 63 60
188 46 48 17
187 16 39 3
187 8 64 20
190 9 51 34
192 37 60 60
191 29 42 38
194 30 43 37
192 44 54 9
196 34 36 10
196 46 66 15
197 22 57 41
196 15 43 3
197 7 39 50
201 22 50 29
202 49 62 34
201 21 42 43
203 18 18 35
203 9 14 10
205 12 74 70
204 41 59 53
207 47 65 57
208 6 16 59
209 18 42 53
208 3 56 7
210 35 74 65
212 1 4 30
214 67 69 24
212 3 28 8
215 20 51 9
215 50 52 68
218 31 46 66
216 16 49 50
220 47 51 53
221 50 57 61
219 71 82 55
220 19 42 75
221 2 65 11
224 52 73 5
225 4 4 69
227 32 69 7
227 21 73 14
229 28 41 20
229 8 38 12
230 32 55 69
231 47 49 74
231 53 64 72
234 57 81 77
235 26 29 52
233 11 16 45
235 26 82 69
236 5 6 81
238 7 66 83
237 41 64 83
239 7 10 89
240 53 65 23
243 16 62 81
242 11 41 79
243 87 88 73
245 52 80 67
246 20 87 90
246 13 47 55
247 15 46 3
250 31 85 50
249 81 93 55
250 10 13 74
251 37 58 2
254 28 83 19
254 25 69 29
256 24 37 60
257 34 69 9
258 73 87 95
259 31 74 61
260 9 87 87
258 7 31 95
259 40 98 76
260 55 77 97
263 71 87 42
265 21 89 27
266 36 59 101
264 83 87 81
265 49 78 46
267 62 87 62
269 42 50 40
268 50 90 84
270 2 40 61
270 3 92 65
273 6 92 92
275 48 55 98
276 62 73 69
274 4 43 78
278 66 77 66
276 57 62 61
279 45 71 78
279 41 64 99
281 56 66 86
283 35 110 98
283 45 68 16
285 5 60 26
286 86 111 41
284 26 51 92
286 48 49 27
286 14 112 70
290 83 111 108
290 73 111 50
292 87 96 53
292 15 58 113
291 1 90 31
294 110 114 52
293 9 54 27
296 81 82 27
295 3 78 10
298 4 63 3
300
1 1 1 0
2 1 2 0
3 2 2 0
4 4 4 3
4 2 4 1
6 1 2 2
6 1 4 1
6 2 5 2
9 2 6 3
10 4 5 1
10 3 6 3
12 7 7 2
12 6 8 1
12 5 5 2
14 7 9 2
14 9 9 2
17 8 10 2
18 3 9 1
18 3 5 1
19 5 12 0
21 6 8 1
22 3 9 1
21 1 7 0
22 2 9 1
23 1 8 0
26 7 15 3
26 10 11 0
28 5 5 3
27 4 8 2
28 1 1 1
30 12 17 2
30 9 13 0
33 11 11 0
34 17 17 3
34 7 15 0
36 4 7 0
35 1 12 3
36 5 16 2
39 17 21 1
40 2 10 3
39 5 7 2
40 6 11 0
42 9 10 0
43 11 24 2
43 8 10 2
46 1 14 1
45 15 24 0
46 18 23 1
49 5 11 0
49 5 8 3
51 4 14 1
52 11 19 3
52 3 10 3
53 1 1 1
55 8 17 0
54 4 11 2
55 3 22 3
56 11 29 3
57 13 25 2
58 5 28 3
60 10 26 3
61 9 16 0
63 11 33 1
62 4 21 0
64 5 34 2
66 10 24 1
67 1 11 0
66 18 20 3
69 6 14 2
70 27 29 3
71 24 34 2
70 9 19 0
72 4 37 3
74 22 27 1
73 30 37 2
76 13 34 3
77 17 24 3
78 3 21 0
79 25 32 3
79 17 25 1
81 34 36 2
80 6 43 2
81 6 35 1
82 34 38 2
85 6 10 3
86 20 40 3
87 8 9 1
88 5 39 1
89 18 36 0
90 16 38 0
91 31 46 0
91 14 33 0
91 20 50 1
93 20 31 0
95 25 38 0
94 5 43 0
96 11 15 1
97 8 19 0
98 17 43 0
100 25 44 3
99 8 24 2
102 26 52 1
102 32 45 3
103 33 50 3
103 16 56 0
105 35 37 2
105 32 35 1
108 16 23 0
108 1 18 2
110 15 40 1
109 10 26 3
110 19 57 2
112 25 55 2
112 20 44 1
115 13 53 2
115 1 4 2
116 5 34 0
116 18 57 2
117 4 27 0
119 16 43 0
119 39 46 2
121 25 33 2
122 28 56 0
122 37 61 3
123 45 48 0
126 40 60 1
127 22 26 1
128 1 35 2
128 5 52 1
129 17 53 0
129 16 64 2
131 12 60 3
133 14 51 3
133 55 65 1
133 25 41 2
135 40 41 3
135 12 70 2
136 20 49 0
138 8 19 1
140 21 63 3
140 2 72 1
142 31 35 2
141 11 39 0
142 29 47 0
143 3 41 2
145 62 76 2
145 51 70 0
147 4 42 3
147 31 67 1
149 1 75 2
149 46 65 3
150 29 66 0
153 47 54 1
153 24 45 1
154 20 57 0
154 16 58 2
155 65 76 0
157 42 48 3
157 25 74 2
158 39 61 0
160 9 58 2
162 22 29 2
161 26 36 0
164 22 31 1
164 28 55 2
166 22 75 1
165 10 26 2
168 64 65 0
169 31 68 2
168 8 39 0
171 33 34 2
171 27 49 3
171 46 52 2
174 4 25 1
174 68 80 2
176 1 51 3
175 56 61 0
177 54 74 3
179 75 81 3
179 47 82 1
179 15 44 0
181 61 82 2
182 20 67 3
183 82 84 2
184 21 82 1
186 39 59 1
186 15 78 1
186 7 65 3
188 9 78 1
189 39 47 2
191 26 42 1
192 25 37 0
193 56 59 0
193 7 70 0
193 30 42 0
195 54 76 0
196 85 94 1
198 76 87 2
199 10 45 3
198 30 72 2
200 91 96 2
200 35 69 0
201 1 55 3
204 40 43 0
203 31 64 3
206 48 54 0
207 85 100 1
206 63 83 3
209 9 36 3
209 47 85 2
211 28 98 3
210 28 88 0
212 100 101 0
213 46 104 0
213 1 77 0
216 53 104 0
215 71 86 2
217 49 68 2
218 78 90 0
220 16 79 0
220 35 107 3
221 32 88 2
223 90 111 0
224 100 108 0
224 57 80 3
224 44 84 3
226 83 94 1
228 62 108 3
228 57 110 1
230 90 94 0
229 48 91 0
232 65 80 0
231 52 54 3
233 3 17 1
235 59 60 2
236 75 118 2
235 3 46 1
238 1 95 1
237 30 77 1
240 21 38 0
239 46 114 2
241 13 82 2
241 81 114 0
244 66 108 1
245 9 45 1
244 41 77 3
245 26 82 3
247 80 123 3
247 22 55 3
250 74 97 0
250 65 88 3
251 15 50 3
253 19 66 2
252 115 117 3
255 28 46 1
255 4 107 2
255 63 65 3
257 81 104 3
257 50 117 2
258 99 124 0
259 5 116 2
260 99 104 0
263 30 103 3
263 30 120 0
264 49 122 2
266 12 90 0
267 75 81 2
266 44 72 1
269 15 27 1
268 48 119 2
269 66 103 2
270 9 127 2
271 99 115 3
274 15 30 2
274 3 44 3
276 50 126 2
277 20 34 2
277 29 113 3
278 47 79 2
280 16 78 3
279 77 125 2
280 39 88 2
281 66 81 0
284 79 117 2
284 64 86 2
286 77 135 1
286 45 122 2
288 14 20 0
289 43 70 0
290 17 54 0
289 47 68 1
291 47 67 2
293 11 58 0
293 131 145 0
293 14 129 3
296 1 123 1
295 37 86 1
296 118 121 3
299 5 130 3
300
1 1 1 0
1 1 1 0
2 1 2 1
3 1 2 1
5 1 2 2
5 1 3 2
5 1 3 0
8 2 3 0
6 1 4 2
7 2 2 0
9 4 5 2
11 3 5 0
11 3 4 1
11 1 1 3
15 1 3 3
13 4 6 1
14 3 5 0
16 3 5 2
17 2 3 0
18 1 4 1
19 4 5 1
22 2 8 3
22 6 8 1
21 2 4 0
25 3 9 3
23 8 9 0
25 2 3 1
26 4 7 3
26 8 10 1
27 2 11 0
29 5 10 2
29 10 11 0
30 4 7 2
32 12 12 1
33 9 12 0
36 4 7 3
35 4 5 2
37 11 14 0
37 6 14 2
37 5 8 1
38 7 10 2
42 3 7 2
42 4 9 2
43 1 7 1
43 4 9 3
45 4 17 3
45 3 7 0
48 10 14 0
48 2 15 3
50 10 16 2
48 14 16 3
49 3 15 3
50 3 9 1
51 7 16 2
54 6 10 1
55 5 12 1
57 7 18 0
55 1 20 2
58 7 17 2
58 12 19 0
59 13 21 3
62 23 23 1
63 6 10 0
61 8 17 3
64 12 22 1
66 2 17 2
65 11 15 3
67 6 21 2
67 6 21 2
70 8 12 3
69 2 27 2
71 1 20 3
70 16 20 0
74 17 25 1
72 6 13 3
76 4 11 2
77 6 21 1
77 24 31 1
76 6 15 2
80 13 25 1
78 15 17 2
80 4 6 3
80 18 20 2
84 18 28 3
82 1 23 2
84 7 21 2
87 3 31 1
85 10 19 0
89 15 24 2
88 2 3 1
89 22 25 3
91 6 28 2
93 6 20 2
94 1 35 3
95 11 38 3
94 7 17 0
95 12 14 2
97 25 30 3
98 34 39 3
99 13 38 2
99 17 33 3
101 4 11 0
103 1 20 3
102 2 35 2
103 6 23 2
104 14 30 0
107 20 32 1
105 19 20 0
107 2 4 1
109 17 41 0
108 1 30 2
109 2 30 2
110 16 35 3
112 40 42 1
113 2 35 2
116 15 42 3
114 41 44 3
115 4 4 3
118 4 33 3
120 27 44 3
119 34 41 1
122 24 26 1
120 7 37 2
122 33 44 0
124 22 27 2
123 4 41 2
127 16 23 3
127 3 32 2
127 28 42 3
129 14 40 1
131 44 50 0
131 23 41 3
132 12 21 2
132 15 19 1
134 9 11 1
133 4 52 2
134 17 44 2
138 1 2 1
139 5 19 0
140 34 40 3
139 5 33 2
139 25 36 3
141 14 19 2
143 4 28 0
143 27 46 1
145 2 22 0
147 9 46 0
145 12 48 1
148 36 37 2
147 41 48 1
149 55 59 1
149 34 52 3
150 48 52 1
153 10 15 2
152 1 57 1
153 3 50 0
156 8 26 3
157 9 51 2
157 22 48 3
158 12 12 1
160 15 49 1
162 3 61 0
162 18 55 2
161 18 46 1
162 14 46 1
164 26 48 3
166 12 24 0
166 41 49 3
169 14 59 2
169 2 45 2
168 46 50 1
172 30 63 3
171 10 39 3
173 3 51 0
175 23 26 3
174 48 59 3
176 6 10 0
178 36 52 3
179 31 34 2
179 26 58 3
179 3 43 2
180 25 57 0
181 5 38 1
182 11 17 1
182 6 45 2
185 14 19 0
186 18 18 2
186 22 32 0
189 2 14 2
188 41 58 0
188 43 52 1
189 30 46 0
190 54 56 0
192 18 52 1
193 44 57 1
196 20 58 3
197 10 28 2
197 1 47 3
199 42 78 0
200 12 16 1
201 14 15 0
202 14 80 1
202 30 44 2
201 74 80 0
205 57 65 2
205 2 61 2
206 20 45 1
206 46 49 0
207 18 73 3
209 16 18 0
211 8 15 1
210 16 44 2
210 3 27 3
213 21 46 0
214 9 22 1
216 16 24 3
215 3 74 0
217 15 21 3
216 27 66 0
219 73 74 2
219 28 63 1
220 28 29 2
223 18 43 0
222 66 83 1
225 6 30 1
224 9 46 2
226 24 47 0
227 26 73 3
226 21 35 3
228 17 31 3
228 24 25 1
231 5 74 0
231 1 48 2
231 50 81 0
233 82 91 0
235 19 73 2
235 65 79 2
237 40 67 0
238 50 77 0
239 18 53 1
238 57 60 0
240 47 66 2
240 6 38 2
243 19 50 3
243 14 33 1
244 37 42 1
245 30 63 3
248 15 27 3
249 7 98 3
247 14 45 3
248 35 69 2
250 82 94 1
250 94 96 1
253 66 68 1
252 55 94 3
255 5 81 3
257 9 48 2
256 30 80 0
256 2 98 1
260 22 96 0
259 35 98 1
259 27 49 1
263 20 37 3
263 55 64 0
265 12 71 2
266 13 44 1
265 25 89 3
266 73 99 1
267 24 75 2
267 11 37 0
271 23 36 1
269 3 73 3
271 31 90 2
273 4 40 1
274 52 106 3
276 10 69 0
277 59 98 0
276 17 48 3
276 40 50 1
280 65 73 3
279 2 54 3
282 69 110 1
280 68 85 2
281 71 93 0
282 5 92 2
283 33 68 1
285 34 56 0
286 55 95 1
287 26 68 0
289 24 56 0
290 51 82 3
290 9 83 2
293 83 91 1
291 43 84 3
295 18 102 2
295 88 100 1
296 36 60 2
297 92 111 2
297 3 64 3
300
1 1 1 0
2 1 2 1
2 1 1 0
4 1 2 2
3 3 3 0
5 3 4 3
5 4 4 1
6 2 3 0
8 2 5 4
10 2 6 0
10 5 6 0
11 1 5 5
13 7 7 2
13 3 6 4
14 2 7 7
16 1 10 2
17 1 9 7
16 4 9 1
19 2 6 5
18 1 1 8
20 2 5 0
22 4 12 10
21 5 10 1
24 9 12 4
25 2 5 6
24 2 6 8
25 1 10 11
28 3 3 11
27 5 8 14
29 8 12 15
31 5 8 15
30 4 6 6
31 10 17 17
34 10 15 9
34 2 18 8
36 4 17 3
37 5 14 8
37 7 10 11
37 20 21 15
38 3 14 18
40 3 8 4
41 2 16 10
43 6 17 4
43 11 11 7
43 6 23 22
46 12 12 11
46 14 19 0
47 4 10 14
48 4 18 2
49 13 20 14
49 11 17 9
51 7 10 9
51 1 22 15
52 15 24 15
54 8 12 4
55 11 13 18
57 5 26 11
58 6 21 10
58 10 14 27
59 8 10 27
60 29 30 24
61 3 15 20
61 4 8 10
63 17 27 16
64 27 30 9
66 6 8 27
65 23 33 0
67 14 16 16
69 10 37 17
70 7 35 23
69 1 15 21
71 11 30 18
73 15 29 6
72 11 25 24
75 2 19 6
75 33 37 29
76 27 40 20
76 11 14 23
79 1 31 14
79 13 41 39
80 9 28 1
80 6 33 17
81 36 39 13
84 37 37 37
85 25 42 15
84 3 23 4
87 13 43 22
86 13 19 22
88 11 14 8
89 24 46 24
90 7 28 30
91 16 47 42
93 33 43 0
93 15 16 36
95 2 49 0
95 1 35 21
97 21 42 25
97 18 43 48
99 15 50 22
100 13 40 30
99 5 32 15
100 17 33 4
103 21 35 35
103 23 41 18
103 27 30 21
106 5 50 31
106 11 37 2
108 20 30 41
107 9 22 28
110 34 49 22
109 8 16 18
111 5 44 16
112 43 52 16
114 16 38 50
115 2 8 14
114 37 53 17
115 35 49 0
117 7 32 15
117 33 50 52
120 8 54 15
121 42 56 5
120 39 51 36
123 22 49 17
122 14 30 13
125 42 62 14
126 47 56 5
125 3 45 45
128 15 46 44
128 12 47 38
129 24 60 18
130 19 48 54
132 20 23 8
132 4 39 21
134 1 30 41
133 12 30 51
135 11 39 25
137 14 29 46
136 37 54 65
139 33 58 67
138 9 44 15
140 3 30 29
142 42 47 66
143 29 72 23
144 32 64 70
144 49 63 70
145 43 69 62
147 8 17 1
147 28 45 49
149 52 59 52
149 8 61 14
150 42 43 64
151 7 46 69
153 3 52 22
153 48 66 51
155 23 38 39
156 14 40 27
156 29 36 69
157 3 71 32
157 6 49 42
158 51 57 23
160 23 27 32
162 55 58 41
161 19 38 13
164 18 50 28
165 11 59 13
166 17 76 81
166 1 32 10
167 51 80 78
168 22 72 21
169 27 30 50
171 61 69 20
170 53 82 14
173 16 51 52
174 15 69 6
173 22 58 3
174 45 62 76
177 19 64 21
178 26 55 88
177 17 51 71
179 4 56 10
179 45 78 39
181 60 80 10
182 45 75 85
183 8 28 66
184 78 80 82
186 37 66 38
186 40 51 3
186 14 74 68
187 2 67 3
190 4 29 32
191 70 86 43
192 33 58 40
192 7 22 78
193 1 38 84
193 11 83 37
196 44 61 23
197 88 98 46
197 4 31 90
197 27 42 76
198 28 54 68
200 51 89 12
200 1 44 70
202 14 86 38
202 27 30 39
203 6 100 27
206 2 74 28
205 77 89 19
208 24 38 45
207 93 103 5
210 17 46 15
209 5 33 28
210 61 83 84
212 10 41 85
213 6 35 53
214 46 74 62
214 1 105 2
215 25 50 48
216 9 86 32
217 88 108 68
218 16 52 30
220 68 97 104
220 30 70 41
221 45 47 34
223 27 57 13
225 27 103 55
226 96 113 2
227 56 88 91
228 60 87 100
228 54 71 93
228 66 116 100
231 6 105 104
230 8 86 78
231 7 17 0
233 27 63 22
234 23 105 94
234 34 115 70
236 42 44 20
237 1 8 101
238 46 70 85
240 33 110 94
240 78 117 60
240 1 22 102
241 71 118 64
243 31 48 83
244 96 99 97
244 30 32 6
245 79 92 77
246 69 114 63
248 16 78 0
250 30 104 51
251 49 87 11
252 31 127 27
252 51 69 17
254 6 76 86
253 24 73 33
256 55 86 107
255 104 127 113
257 18 100 31
257 36 62 4
259 12 60 76
259 39 125 56
261 51 64 57
262 17 129 129
264 17 128 14
264 12 16 56
265 92 117 68
265 34 98 130
266 25 93 131
267 104 127 89
268 89 96 118
270 60 63 107
272 54 79 101
271 5 72 96
274 32 43 112
274 15 42 106
275 32 51 32
275 52 115 133
276 39 100 86
278 50 78 12
279 55 136 22
279 49 54 2
280 99 135 31
283 39 74 101
283 52 71 29
285 71 84 49
285 29 112 31
287 53 88 98
287 53 98 30
288 76 117 109
288 39 137 43
290 22 74 27
291 49 105 107
293 11 70 27
294 1 15 72
294 137 145 79
294 12 62 42
296 5 82 120
297 3 82 131
297 133 138 105
Sample 2 Output
2 28 1 1 28 166 0 29 742 30 1 1483 166 2586 0 19 195 2420 5984 195 5789 937 2785 584 541 742 583 583 12843 2039 12815 1 2419 908 10395 124 16169 35562 30215 0 29 32115 1502 2439 57 28331 166 8422 13384 204 26199 9 9 23735 8394 44899 4494 0 2439 16802 4494 1 149898 0 474707 1 324791 1 53714 53715 175273 132930 62 196179 30922 64527 58800 18845 135715 46989 139103 42891 156683 0 237301 28739 832443 42891 29 42858 4 204182 268999 150468 150468 217828 0 1035573 745 13275 560866 0 745 500216 118972 13387 13387 3648272 658848 1840408 3 2410 0 97561 40779 56782 0 1395875 3 3419624 0 1979426 2346998 0 192402 43195 2158161 0 149207 16277 0 883868 8049 0 8228 0 1879046 658925 2431007 55141 1249283 23163768 0 134978 17358268 35686 6996641 200405 35686 0 4418183 111640 6553434 52778 813581 391 4395059 13275 1247539 1316585 2061946 354650 159279 2094332 183043 12242665 178311 1676048 7817352 57159374 141717 2182672 147284 3787431 0 1439632 85813 9115 0 0 85813 8011606 29208814 0 0 27321719 16169 500126 66387481 11322155 9471403 0 968756 785314 75068640 4347707 1341192 1732746 68131382 2588184 8432508 1280704 1680718 14577 5454593 14577 1680718 93391 51295 0 265088406 51295 7153356 57273194 124438089 69844547 53590 53590 1124776 1124776 0 53590 0 133583610 1618599 58198 10986611 230515786 60862934 201259640 0 0 34864 34864 2 0 152161 2 4664 0 2 1258749 0 27193 55816 2833708 0 53591 558497526 6818377 53591 0 221318663 77091011 76645419 829944 70391503 994 1041047 0 0 1864876 0 152395921 288896861 86 157013 81100958 4944298 60166954 96345 0 2784584 0 0 165345 626302 1439883 192402 626302 0 626302 43196 122518936 49295029 1157500 0 320028 5590049 2391 3278221 1066374 0 639433204 37489603 182835079 219979924 638955310 793685616
18 503 17586 1 17567 0 18107 16524 16002 18089 612901 18 3145158 17586 522 3144114 43595579 517802536 3774061 148939670 578186631 839087774 717255960 717272484 689785012 402787159 148972196 148939670 753422683 0 68200 770297264 385923609 228613002 154165449 688593922 982018099 166601118 390392503 426512720 268536200 154951093 419030052 347816389 387903187 961120736 50565952 273082306 328249235 942396341 262985553 332953376 633898000 857021017 439169393 710469083 417851624 299741956 286626813 670126137 299062482 629602267 445794448 466653064 587303205 464453180 892347689 124951330 265686739 470486520 134611851 758825287 994780454 40589111 530150900 526324641 385419688 179539797 961088667 848150780 424611047 980459035 979777933 762369814 711856060 166526718 669853600 459750974 307098285 240527460 299706300 475410284 202783686 480795608 984395204 672783510 906214669 480813808 538657422 594660329 365090638 890798581 6471962 389882488 425865558 711159070 764198814 462077897 94036181 884395373 836006147 425865539 954155687 78862555 641703203 837417017 94981424 863405290 609384659 432490167 273196988 382270731 220952646 881564848 294068358 226748059 754265357 353990794 468480124 918845620 563029304 666228966 830970268 47165991 672895586 301484051 511556816 223759928 888290577 238693036 909679323 234640309 724438363 486630878 519328466 169633903 674375630 946730662 646620178 748389471 77078573 390426327 338216216 656177732 498513444 444905916 236698582 244303491 984804499 365979087 772524720 435642911 819679277 165804252 799187042 860042567 573052729 155632053 833109839 417688671 155352965 56508384 995331951 381775297 965169693 819661368 175806915 997447660 824052610 419958646 594725861 538961272 203995865 49884851 799555852 686218790 189782286 980048398 369294449 858505508 975177197 442481599 623190673 137413467 357526918 177705197 328459742 193048829 747974982 836422937 50530278 351522928 223187900 22161096 313349957 310721327 145558418 450267654 363377488 785013570 566364046 71223537 32526 826531054 978426681 167607004 469526386 237696262 907075067 140013296 261759096 647909210 57021383 717290051 440228728 429648217 849114765 81217332 34647669 56363336 295416420 380737691 679921835 927217039 397422729 436688947 183644352 309656550 369199056 495268350 261706916 335060944 723482567 558964880 791344251 558037787 925656399 644048289 668433088 734927242 560979774 210536245 876733184 672724034 872652574 762839667 754954784 180236902 178037371 75032949 996127629 986112455 425928812 468626485 167340565 306732231 645679237 297967807 707823637 451469385 882171736 277858655 393546679 732876982 120029277 515021373 44261425 540779681 538027602 811410863 566618390 419407773 809836432 895013471 442819453 202276334 729004289 466271799 523699750 643233474 613037858 544365749 928603951 644396792 108771927 799447419 656797308 422162947 140699499
2 25 1 24 1 20 125 75 26 2572 26 2672 2347 101 221 2622 262780 10609 5244 262711 8195 5534 69 1046043 252853 27351 525491 15746915 530460 27302 95298226 5225463 530410 342492332 5225437 5225367 342492331 70 1576523 1824387 741482499 820077187 112869528 809205574 455099080 797859180 291902778 364506543 386370022 349435236 2616 362930090 711329955 833869511 539267950 536652996 364338138 203074191 173886392 825766009 349154364 973475334 120472521 712891562 66167520 266552743 539267950 11914646 515394037 361385818 145984 751503276 910203148 455366779 245310539 875419556 952877238 530480 978444241 852159192 201626815 344634909 646780148 964993848 154105185 769254322 636218660 423896592 201525688 877993865 453790326 460203748 991321857 801224252 33302835 692713458 453197773 637109276 4989 331570009 32917212 599939819 794995786 500841957 188882771 118608665 44998377 500429683 153035986 753079798 494379263 193365683 423019078 89138390 793076483 278759332 187898215 89133451 306504239 38980172 365616259 898619038 893176881 362930090 980652320 453761172 173084993 333548285 590678297 264247015 916762493 76293173 250576851 664609145 628516030 268871278 288599481 56646754 1219382 780551590 275457802 527637072 388003213 389191640 241382955 132861652 40794521 252261590 891986159 834587890 762281407 331882036 796282657 233327889 16296002 652244283 460931004 783355343 567614858 617886969 393701899 539491341 75857887 284338684 141923444 616402655 568810173 323488538 866661590 392801273 96283925 434026187 93592566 360986156 508863281 202824584 36644143 944010682 636726305 794488849 625705730 371882449 791625633 630719394 281927880 847974220 382264279 589266517 727727581 950037863 373824015 905715000 388134585 708383387 569926160 129980925 292994843 544286321 5252318 355742237 857327206 108104949 218912145 81957300 133048067 946885817 853053690 952500964 891778739 981495893 90199625 109621199 411199913 823024914 38280025 258233549 520761238 264274023 309965770 85730477 701629732 608520550 965311673 941110771 407078334 186411711 681898970 281557055 327495676 967726221 795012343 860790750 690698405 476569205 112874491 650738670 13692791 846832963 468246718 542104454 27499869 685435401 585855376 868000355 35773758 930845083 239089735 869911756 206944065 82870863 382988041 618649950 267699 764735111 770193998 786807544 850939318 866946508 972038200 614201737 745363097 723804125 323284494 472138369 440779171 236638145 458847315 135000873 366043785 304166473 295925068 227508474 935779045 883093823 721522274 961591300 584843273 84914757 238805346 778519314 666113958 931956928 142909965 65860216 539804828 222607205 925337479 578857483 792103451 31387119 243604525 909375005 314530617 255818088 909216230 897578638 288087681 566439688 109365588
19 2 35 16 22 1 15 21 14 173 20 87 87 51 68 488 128 340 68 77 636 54 482 90 0 0 10 10 0 10 0 0 10 444 2975 2975 1210 0 20 275 120 2145 1547 482 275 6084 9926 5602 8895 2043 4459 10 1108 3174 7180 2037 3671 7821 51 566 51 2123 1783 2725 1783 1494 1188 13689 8630 3835 5059 14090 16756 5059 44948 253 1690 2964 55745 216 45182 11228 35865 469 14044 78140 8979 9269 11953 9269 0 289 1704 2019 191289 37562 11315 117 171498 7849 48329 171048 0 35571 87148 26213 160724 4106 31135 54646 57022 120660 109993 0 0 108299 11160 135057 898 317252 165736 18802 117773 161027 10429 1450 1813 7694 16038 121998 79 33130 149101 0 79 126955 0 79 79 803646 3319 355 158687 269 0 1588 804351 26122 9600 1583474 0 543 807752 57948 168327 696174 1186 192793 48752 4395609 19319 19319 5125332 3536199 6602149 0 4974369 260 3586649 26000 26000 1857959 45623 1956458 1763767 269 1779466 269 0 8189977 193708 45664 4109 0 15492 4067550 667093 15591 38229932 2364472 2364472 3064570 0 0 2730526 986588 1709 0 111257 0 2406852 55040 1761858 73151 9258434 5687656 73151 43947 34285137 34283502 1713622 0 43947 0 321945 92580260 744599 3559992 147808 2854388 0 3659596 49247 28619905 1008799 16788 14969 0 0 14969 77 37254 101161820 34881341 59477 191234 1733319 0 123180 69251 158347 5345 426017 188081 23603 198086 609912 824996 101921714 7913353 119394631 113317102 2580093 1770 35103565 8915 1770 84870638 34119178 0 1961188 164376 35 220453479 0 200312 67 0 44163 1811 0 0 36713 66 36647 60369416 66 736018 195447010 23458087 12244335 162942974 0 255549044 808183 222614885 199741 35530015 25294 88739562 319614652 2258 388346649 0 983 68858558 0 0 1275