#2100. 插线板
插线板
插线板
题目描述
IOI 2014 中国代表队选拔赛暨全国信息学精英赛 第一试 插线板 插线板 【问题描述】 Allison 有非常多的电子设备,比如iMac, iPod, iPhone 和iPad。所以她准备 购买插线板来给电子设备充电。在做了大量的网络调研后,Allison 发现了一款 美丽精巧的天翼牌排插(如左下图所示)。在见到这个插线板的第一眼,Allison 就被它的精美造型所吸引,于是她一次性购买了𝑛个这种型号的插线板。 可是问题也随之而来,Allison 的家中只有一个插座,她需要通过插线板的 连接将电一层一层地导出(如右上图所示)。 插线板的连接方式是树形结构的:每个插线板的插头插在另一个插线板的插 孔中(除了根节点),插线板的连接不允许构成环。 每个插线板有火线,零线,地线三根导线,随着插线板数量的增加、导线的 磨损,电路中的导线与导线之间接触产生的电阻已经到了不能被忽视的地步。 如何来描述插线板的树结构以及导线之间的电阻关系呢?Allison 思考出了 一个数学模型:用𝑎𝑖代表第𝑖个插线板的编号,𝑓𝑖代表第𝑖个插线板的插头所插的 插线板(即𝑎𝑖在树中的父亲),1代表火线,2代表零线,3代表地线,则整个电路 的电阻可以用𝑅(𝑎𝑖, 𝑓𝑖, 𝑥, 𝑦)(𝑥, 𝑦∈{1,2,3})来描述,它代表𝑎𝑖的𝑥线与𝑓𝑖的𝑦线之间 的电阻值(在这个数学模型中,Allison 认为火线和零线也是可能连接并且产生 电阻的)下面是一个例子: 第4 页 共9 页 IOI 2014 中国代表队选拔赛暨全国信息学精英赛 第一试 插线板 由于时间的推移,导线与导线之间的电阻还可能发生变化。现在,Allison 想知道在插线板树形电路中,当前时刻𝑎𝑖插线板的𝑥线和𝑎𝑗插线板的𝑦线之间的电 阻是多少。规定插线板的树根节点不再插向其它插线板,且编号为1。 【输入格式】 输入文件circuit.in 的第一行包含一个正整数𝑛,表示插线板的个数。 接下来4(𝑛−1)行,每4行为一个块。 第𝑖个块的第一行为一个整数𝑓𝑖,表示编号为𝑖+ 1的插线板的父亲为𝑓𝑖插线板。 接下来一个3 × 3的矩阵𝑔𝑥𝑦,第𝑥行第𝑦列表示编号为𝑖+ 1的插线板的𝑥线和 𝑓𝑖的𝑦线之间的电阻的倒数。 接下来一个整数𝑞,表示𝑞个操作数。 接下来𝑞行,每行包含若干个整数。 第一个整数为𝑘,若𝑘= 1,则接下来包含四个整数𝑎𝑖, 𝑥𝑖, 𝑥𝑗, 𝑔,表示将𝑎𝑖插 线板的𝑥𝑖线与𝑎𝑖插线板的父亲𝑓𝑖的𝑥𝑗线之间的电阻值改为𝑔的倒数。保证2 ≤𝑎𝑖≤ 𝑛。 若𝑘= 2,则接下来包含四个整数𝑎𝑖, 𝑥𝑖, 𝑎𝑗, 𝑥𝑗,表示询问𝑎𝑖插线板的𝑥𝑖线与𝑎𝑗插 线板的𝑥𝑗线之间的电阻值的大小。保证𝑎𝑖≠𝑎𝑗。 【输出格式】 输出文件circuit.out。 对于每一个询问,输出一行实数,表示两条线之间的电阻。 选手输出−标准输出 | < 10−3,则被认为该电阻值正确,若所有电阻值皆正确, 若| 标准输出 则获得该测试点的得分。 【样例输入1】 3 1 6 7 1 4 1 8 8 3 3 2 7 5 8 10 5 7 10 5 5 10 1 3 1 2 2 第5 页 共9 页 IOI 2014 中国代表队选拔赛暨全国信息学精英赛 第一试 插线板 1 2 2 3 5 2 3 2 2 2 1 2 3 2 5 1 3 1 2 3 2 1 2 2 3 1 3 2 1 2 2 2 1 1 1 1 2 1 2 5 2 3 1 1 2 【样例输出1】 0.083836 0.095256 0.078828 0.146900 【样例输入输出2】 见选手目录下的circuit/circuit.in 与circuit/circuit.ans。 【数据规模和约定】 对于所有的测试数据,输入保证是一棵树。0 < 输入中电阻的倒数≤10。 测试点编号 特点 1~6 𝑛≤100, 𝑞≤1000,保证输入中只有查询没有修改 7~10 𝑛≤1000, 𝑞≤1000,保证数据是一条链 11~16 𝑛≤10000, 𝑞≤10000,保证树的高度不超过30 17~20 𝑛≤10000, 𝑞≤10000 第6 页 共9 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
100
1
5 1 1
7 4 5
5 3 10
2
6 7 10
1 7 2
6 3 9
1
7 6 4
3 2 9
1 6 5
2
10 10 10
2 9 8
1 8 9
5
2 7 7
9 7 2
10 6 7
5
4 1 2
2 10 8
9 5 2
4
5 1 8
3 3 10
2 8 5
5
6 6 8
3 5 8
9 6 3
7
5 9 9
5 6 2
9 7 1
3
3 8 5
1 8 4
3 6 7
8
3 7 7
8 7 9
10 5 5
4
3 7 3
6 8 10
1 8 6
5
9 7 5
7 7 4
3 6 6
12
5 9 10
7 6 9
6 2 2
12
5 5 9
8 4 7
1 6 7
7
3 3 4
6 8 10
5 9 2
10
9 8 8
8 5 10
8 5 7
1
2 7 9
8 9 1
4 4 4
3
4 2 3
4 10 8
4 3 5
15
10 3 6
5 7 1
9 4 5
1
6 2 7
4 4 2
10 6 3
6
3 10 6
10 9 9
3 10 8
3
8 9 10
8 5 2
1 9 1
22
7 10 4
2 4 5
5 7 7
23
10 8 2
5 1 10
5 2 2
8
3 3 5
10 10 6
1 3 10
13
7 5 4
1 9 9
2 6 1
22
10 8 7
7 7 5
3 10 10
15
3 8 6
4 8 9
6 2 6
25
2 1 5
8 7 1
3 8 9
31
10 4 4
4 8 5
1 7 4
26
7 5 2
3 2 5
3 3 5
18
1 10 4
4 10 8
4 7 2
7
7 10 6
6 9 9
10 2 3
35
7 5 6
10 10 7
3 2 10
31
8 5 10
7 9 1
6 2 1
17
1 3 9
2 1 9
10 3 9
18
1 5 3
3 6 6
3 1 9
7
10 10 3
8 7 2
10 4 1
13
3 6 9
1 4 7
3 6 2
3
9 1 10
9 5 7
10 7 10
17
1 5 7
6 5 9
3 4 4
17
2 5 1
9 6 5
10 8 8
36
3 8 7
4 1 6
9 2 2
5
9 4 6
2 1 6
3 6 4
2
9 3 1
5 3 10
6 7 2
38
6 8 6
5 1 1
8 6 7
23
2 8 10
3 2 8
3 1 3
1
4 9 7
6 1 9
2 7 9
40
3 2 1
3 2 7
5 5 8
25
2 1 3
8 2 3
8 4 10
28
10 10 8
2 7 5
10 6 7
32
6 8 3
5 5 3
3 10 8
25
7 1 1
8 6 1
7 7 1
55
2 4 1
2 8 1
4 5 10
50
4 3 3
6 3 1
2 1 5
5
5 10 2
7 7 3
9 1 9
6
9 9 5
6 6 10
2 3 8
2
4 1 4
7 8 9
8 1 6
10
6 1 8
9 4 10
4 6 3
23
5 1 4
7 1 3
4 6 3
2
6 2 10
3 3 2
10 2 2
9
1 1 5
10 3 7
1 2 10
23
9 3 2
2 7 5
6 9 10
34
10 6 3
3 4 9
2 6 4
56
8 8 10
3 6 7
7 7 6
25
9 5 4
8 3 2
2 8 8
49
2 3 5
4 5 5
9 3 10
53
2 2 4
4 8 3
5 10 10
57
8 1 5
3 2 1
6 9 1
39
3 2 4
2 8 7
9 5 2
21
3 3 10
9 1 4
1 2 1
8
10 2 5
6 8 8
1 1 5
35
8 4 5
5 1 2
5 7 6
74
10 1 2
6 9 4
4 10 5
64
7 10 1
10 8 5
4 5 10
37
2 7 2
7 8 9
4 1 10
50
8 8 8
8 9 4
1 9 3
25
1 8 5
4 4 9
3 6 5
64
6 3 9
2 9 9
2 1 10
60
4 9 1
4 7 6
5 2 2
21
3 1 9
4 7 10
7 6 3
12
5 7 10
10 7 8
8 5 6
26
3 9 2
4 10 8
2 5 1
64
4 7 2
1 5 2
8 6 6
42
5 2 7
3 2 7
10 3 8
82
3 6 5
7 2 4
2 4 8
87
10 3 4
4 5 7
3 1 5
17
1 7 7
1 10 10
1 6 2
36
2 10 5
4 10 3
4 1 6
80
6 9 8
2 10 9
9 7 2
90
5 9 6
1 6 6
3 1 10
89
7 5 4
2 2 4
2 9 5
9
1 7 4
1 3 7
6 7 5
83
9 4 1
8 10 3
4 7 2
59
3 5 4
5 8 4
7 3 7
2
5 3 7
1 10 6
1 4 6
51
3 10 10
2 1 6
4 1 4
28
9 9 2
7 5 1
2 9 4
1000
1 52 3 3 2
2 82 1 98 3
1 6 3 2 4
2 52 3 29 2
2 25 1 96 1
1 15 3 1 7
2 11 2 74 3
2 90 1 100 3
2 75 1 72 3
2 8 2 21 3
2 43 2 6 1
1 20 2 2 9
2 74 1 77 1
1 64 1 1 7
2 87 3 22 1
2 12 1 78 2
2 66 2 38 2
1 66 2 1 1
1 42 1 2 4
2 23 1 16 2
1 95 3 1 10
2 59 1 2 2
2 24 3 36 3
2 6 1 32 2
2 26 3 86 3
2 24 3 14 2
2 27 3 37 3
2 65 3 1 3
1 8 3 2 1
2 5 2 95 3
2 89 3 35 1
2 85 1 57 2
1 40 1 1 4
2 46 1 11 3
2 3 2 4 2
2 56 1 52 2
2 79 1 59 3
2 15 1 2 2
2 83 3 34 3
1 51 1 2 2
2 22 2 61 3
1 84 1 1 7
1 9 3 2 5
2 41 3 60 2
1 42 3 3 4
2 30 2 11 3
1 66 3 2 6
2 13 3 84 3
2 74 3 29 3
1 77 2 2 4
2 54 2 23 1
1 15 3 2 8
1 14 3 1 6
1 94 2 3 3
1 98 2 2 8
1 13 2 1 6
1 37 1 2 7
1 92 3 2 2
2 69 3 48 1
1 65 1 1 7
1 96 3 3 6
2 31 3 89 1
2 61 3 89 3
2 88 3 67 3
2 14 1 81 1
2 83 2 81 3
2 64 2 51 2
2 44 1 82 3
2 92 3 43 1
2 99 2 29 2
1 95 3 1 4
2 51 3 11 1
2 79 2 29 1
1 72 1 1 2
2 9 3 80 1
1 15 3 2 3
1 9 2 2 10
2 7 1 79 2
1 45 3 1 8
1 21 3 1 7
2 93 1 75 1
2 7 1 14 2
1 61 1 3 4
1 73 2 3 5
1 47 1 3 9
2 79 1 37 2
1 32 2 2 4
1 68 3 3 10
2 44 2 62 3
1 24 3 1 10
1 32 1 3 10
2 83 2 65 2
2 88 3 74 2
2 14 3 29 2
2 71 3 2 1
1 75 3 3 2
1 83 1 2 8
1 44 3 1 7
2 29 3 53 1
2 46 1 13 1
2 68 3 18 3
1 31 3 3 1
2 33 3 42 2
1 99 3 3 2
1 87 2 3 2
2 29 2 96 3
1 72 2 3 5
1 90 3 3 8
1 97 2 2 2
1 27 2 3 2
1 5 2 2 10
1 39 1 2 3
1 73 1 3 1
2 85 2 80 3
2 91 1 8 3
2 83 3 4 2
2 5 2 31 2
2 89 2 49 2
1 60 1 2 7
2 97 1 6 1
1 67 1 3 5
1 64 3 3 7
2 32 2 48 3
2 23 2 97 1
2 29 2 73 2
1 16 1 1 3
1 89 3 1 3
1 34 3 1 3
1 80 2 1 5
2 6 2 95 3
2 77 3 58 1
2 63 3 23 1
2 52 3 57 1
2 51 3 1 2
1 84 2 2 8
2 83 1 32 2
1 69 3 2 9
1 45 2 1 9
2 68 2 53 2
1 93 3 1 8
2 48 2 61 3
1 54 3 3 5
2 84 3 16 3
1 5 2 1 9
2 43 2 44 2
2 36 3 28 3
1 76 2 3 7
1 71 1 3 3
2 65 2 88 3
1 89 2 2 10
2 73 3 44 3
2 13 1 40 2
2 35 3 83 3
2 50 2 97 2
1 47 2 2 10
2 93 1 32 1
1 53 2 1 7
1 58 1 3 9
1 9 1 3 9
2 9 2 12 3
2 89 2 58 2
1 86 2 3 10
2 13 2 91 3
1 8 1 3 3
1 6 2 1 10
1 32 2 3 3
2 40 2 85 2
2 13 2 84 3
2 80 3 34 3
1 91 2 2 8
1 60 2 3 9
2 47 1 96 3
1 28 3 1 8
2 61 2 20 3
1 93 2 1 9
1 39 2 3 4
2 38 1 78 3
2 60 2 95 3
2 85 3 28 3
1 76 2 3 1
1 20 2 2 3
2 27 1 100 2
1 86 3 2 9
2 62 3 15 3
2 41 3 52 1
1 5 2 1 10
1 20 2 1 5
1 86 1 2 8
1 37 2 2 3
2 97 3 36 1
2 41 2 34 1
2 78 3 31 3
2 25 1 23 1
1 59 2 1 5
2 77 1 71 1
1 74 1 3 5
2 68 1 67 1
1 17 2 3 1
2 2 1 97 2
2 40 1 1 1
2 44 2 71 3
1 9 2 1 2
1 77 3 1 9
1 66 3 2 10
2 3 2 7 1
2 74 2 24 2
1 46 3 3 2
2 60 3 87 3
2 6 3 97 1
2 78 2 85 3
1 74 1 3 7
1 22 3 1 8
1 18 3 3 6
1 52 2 2 4
2 30 3 56 3
1 81 1 3 7
1 95 1 2 7
2 97 2 45 3
1 71 1 2 7
2 73 1 76 1
1 53 3 3 9
1 19 3 3 2
1 69 2 2 1
1 99 1 2 3
1 34 3 2 7
1 29 2 3 9
1 82 2 3 3
1 68 3 1 7
1 63 3 2 2
1 36 3 2 6
1 94 2 1 6
2 44 1 13 2
1 42 2 3 10
1 61 1 2 10
1 28 3 3 4
2 11 3 23 1
2 87 2 84 2
1 53 2 1 9
2 24 1 47 3
1 2 2 1 4
1 21 2 1 9
1 40 3 3 3
2 23 1 56 3
2 37 2 8 1
1 40 3 2 6
2 40 3 100 3
1 99 1 3 4
2 90 3 47 3
2 15 3 74 3
1 64 1 1 5
2 15 2 42 1
1 77 1 3 9
2 86 3 95 1
1 72 2 1 6
2 60 1 81 3
2 70 1 77 2
2 86 2 70 3
2 20 2 48 2
2 25 2 46 2
2 60 3 92 2
2 69 1 10 1
2 44 2 60 1
1 35 1 1 9
1 31 2 2 4
1 28 2 3 1
2 81 1 35 2
1 11 2 2 10
2 22 2 71 1
2 46 2 89 1
2 86 3 2 1
2 90 2 99 1
2 30 1 32 2
2 22 2 14 3
2 75 2 41 2
1 72 2 2 4
2 51 2 9 3
1 92 1 2 10
2 84 2 2 2
1 28 2 3 8
2 64 2 10 1
2 3 1 8 3
1 20 3 3 10
1 13 1 1 10
2 82 3 70 3
2 32 1 11 2
1 84 2 1 8
2 76 1 96 1
2 18 2 87 2
1 40 2 3 5
1 3 2 3 3
1 14 1 3 4
1 85 2 1 5
1 48 1 3 2
1 8 3 1 6
1 72 1 2 3
1 24 2 2 4
1 93 2 2 5
2 52 2 13 2
2 100 3 77 2
1 41 3 2 2
1 20 1 2 5
1 96 2 2 3
1 37 2 2 2
2 31 1 60 1
1 27 1 3 7
2 61 2 55 1
2 73 3 91 1
2 57 1 42 1
1 91 2 1 4
2 34 3 70 1
1 21 1 3 2
1 96 2 3 4
1 91 3 2 1
2 5 1 72 3
1 48 3 1 5
1 4 2 3 10
2 73 2 30 3
1 20 3 1 4
1 27 1 3 9
2 8 2 36 2
2 61 2 54 3
2 1 1 65 1
2 93 1 71 3
2 79 2 73 1
2 68 2 9 1
2 7 2 51 1
1 81 2 2 9
2 41 2 77 2
1 85 2 1 7
2 59 2 90 1
1 50 1 1 5
2 74 3 16 3
2 51 2 90 1
2 82 2 8 1
2 28 1 99 1
1 71 3 2 1
2 60 3 52 1
2 84 2 92 3
1 37 1 3 10
1 87 2 1 9
2 5 2 93 2
2 38 3 25 2
1 50 1 3 3
2 27 2 63 1
1 11 2 2 7
1 55 2 2 3
2 72 3 10 2
2 13 3 43 2
2 47 2 73 1
2 29 3 2 2
1 79 3 3 6
1 88 2 2 4
1 54 2 1 9
1 43 3 1 1
2 88 2 24 2
2 36 1 47 3
2 68 3 80 1
1 54 2 3 3
1 2 1 3 9
2 35 2 100 2
1 100 2 3 9
1 81 3 2 4
1 65 3 3 4
2 95 3 53 1
2 88 1 12 2
2 35 2 98 1
2 93 1 48 3
2 17 1 54 1
1 82 1 3 2
1 41 3 3 6
2 52 3 41 1
1 8 1 1 7
2 61 3 35 3
2 34 2 10 3
1 76 1 3 2
1 94 3 1 10
1 24 1 1 7
2 49 2 82 3
1 25 3 2 2
2 10 2 72 2
1 11 3 1 2
2 59 1 64 2
2 13 1 1 3
2 93 2 75 3
1 47 1 2 8
1 64 3 1 7
1 22 2 3 10
2 51 2 91 3
2 56 1 49 3
1 17 1 2 6
2 92 2 85 1
2 46 1 42 2
2 49 1 77 1
2 96 3 99 2
2 83 1 17 1
2 17 1 54 1
1 68 2 1 6
2 38 2 78 2
1 36 2 2 6
1 6 3 3 10
2 68 3 16 2
1 50 1 2 5
2 36 3 30 1
2 87 2 2 3
2 24 2 92 1
1 19 2 2 3
1 5 2 2 1
1 65 2 1 1
1 89 1 1 3
1 10 1 1 3
1 100 2 1 7
1 39 2 2 7
1 79 2 2 5
2 36 2 60 1
2 70 2 9 2
1 7 3 2 10
1 15 3 2 1
1 22 1 3 4
2 56 1 4 1
1 9 1 1 8
2 88 1 58 3
2 6 1 19 3
1 29 3 1 10
2 5 3 59 1
2 100 1 58 3
2 97 1 56 1
2 7 3 81 1
1 27 2 3 10
2 42 3 9 3
1 45 2 2 2
1 56 2 3 2
1 12 1 1 5
2 75 2 13 1
1 79 3 3 9
1 33 1 2 2
1 47 3 1 8
2 15 3 64 3
1 71 1 3 10
2 68 1 16 2
1 17 3 2 2
2 57 3 17 2
2 83 1 22 2
2 58 3 90 1
2 56 1 37 1
2 17 1 33 3
1 27 3 2 5
2 98 1 97 2
1 8 3 3 3
2 42 3 71 3
1 45 3 1 1
1 44 1 2 4
2 73 1 52 1
2 33 3 10 1
2 74 2 70 2
2 88 1 7 2
1 4 3 3 3
2 95 1 52 1
2 70 1 63 1
2 42 2 15 1
1 97 1 2 7
1 7 1 3 6
2 5 1 52 2
1 62 2 3 5
1 30 2 2 8
2 50 1 25 1
2 59 1 13 2
2 16 3 3 3
2 93 2 41 3
1 36 3 1 4
2 75 2 48 1
1 63 2 2 5
2 17 2 96 1
1 19 1 3 9
2 19 2 10 1
2 28 3 93 1
1 51 1 1 5
2 84 1 68 2
1 58 3 2 2
1 68 3 1 6
2 12 1 67 3
2 55 1 1 1
1 91 1 1 8
2 84 2 41 2
2 58 2 23 1
1 76 3 3 8
2 5 2 74 3
2 94 1 86 1
1 35 2 1 1
1 8 3 2 2
1 28 1 3 9
1 27 2 1 5
1 77 2 2 2
2 55 2 96 2
1 25 2 1 8
1 34 1 2 8
2 28 2 85 3
2 69 1 35 3
1 73 1 3 4
1 16 3 1 5
1 22 1 1 3
1 20 2 3 2
1 13 3 1 4
1 43 3 2 7
1 29 2 2 3
2 90 3 4 3
1 8 3 1 7
2 43 1 30 2
2 96 3 9 3
2 38 2 28 1
2 94 3 55 3
2 24 3 54 3
2 95 1 28 2
1 68 1 1 6
2 84 3 57 3
1 87 2 2 3
2 69 3 75 2
2 25 3 61 2
2 77 3 43 2
1 82 2 3 3
2 50 2 39 3
1 67 1 2 6
2 59 3 89 2
1 30 2 1 10
2 47 3 37 1
2 67 1 34 3
2 28 1 57 3
2 65 2 40 2
1 32 3 2 4
1 60 1 1 6
1 83 1 2 6
1 49 2 1 9
1 87 2 1 4
1 82 3 3 1
2 35 3 17 1
2 14 1 90 1
2 2 1 3 3
2 83 3 45 3
2 73 1 33 1
1 38 3 3 4
2 95 3 68 3
2 2 2 73 3
1 63 3 2 4
1 41 2 3 8
1 60 3 3 4
2 3 1 87 2
2 32 1 96 2
2 79 1 38 2
1 5 1 2 4
2 69 1 84 2
2 25 1 31 2
1 24 1 1 2
1 75 2 1 2
1 72 1 3 6
1 7 1 2 7
1 57 1 1 9
1 22 3 1 5
2 84 1 57 3
2 98 1 23 3
2 33 3 66 1
2 35 2 69 3
1 34 1 2 3
2 69 3 51 1
1 57 1 2 6
2 36 1 66 3
2 77 1 86 2
1 12 2 2 3
2 98 3 20 2
1 56 1 1 3
2 60 3 90 1
2 16 3 31 3
2 10 3 27 3
1 17 1 2 8
2 71 3 29 2
2 79 1 43 1
2 83 1 20 2
2 99 1 64 2
2 98 2 82 1
2 11 3 78 3
2 22 2 78 1
2 60 1 16 2
2 26 1 89 3
1 58 3 3 5
2 49 2 57 2
1 34 1 1 7
1 98 2 2 1
2 85 3 21 1
2 77 3 87 1
2 90 3 31 2
2 99 3 54 2
1 19 1 1 3
1 19 2 2 2
2 84 3 38 1
2 65 2 27 1
1 77 2 3 3
1 65 1 2 5
2 53 1 9 2
1 91 2 2 7
2 76 2 6 3
1 53 2 3 6
2 63 1 11 1
2 81 3 87 1
2 9 3 29 3
2 53 1 31 1
2 50 1 79 2
2 36 3 26 2
2 40 3 33 3
2 21 1 42 3
2 12 1 19 3
1 24 3 1 9
2 24 2 37 1
1 68 3 1 7
1 21 3 2 1
2 56 1 14 3
1 73 2 2 6
2 46 2 92 3
1 23 2 3 4
2 28 1 22 2
1 53 3 1 7
2 69 3 13 1
2 44 1 25 2
1 58 1 2 6
1 75 2 2 3
2 81 2 66 1
2 61 2 96 1
2 86 2 51 3
2 20 2 55 1
1 13 2 3 7
1 69 2 2 1
2 50 2 52 3
2 66 1 67 2
2 4 1 56 3
1 89 1 1 9
2 1 2 4 3
2 81 3 79 3
1 2 1 1 5
2 62 2 20 2
2 55 3 69 3
1 47 3 3 1
2 98 2 79 1
2 87 1 70 2
1 49 2 3 10
2 95 3 29 2
1 69 2 2 1
2 3 1 2 1
1 44 1 2 7
1 94 1 2 9
1 3 3 2 6
2 92 1 70 1
2 25 3 34 3
2 19 3 77 1
1 39 2 2 10
1 41 2 1 6
1 64 1 3 10
1 32 2 3 1
1 6 3 1 9
1 95 3 1 5
2 42 3 68 3
2 51 2 32 1
2 28 1 94 1
2 6 3 43 1
1 83 1 2 5
1 62 2 3 9
2 32 1 64 3
2 99 3 67 1
2 99 1 86 2
2 96 1 39 3
1 41 2 3 7
2 51 1 76 2
1 43 2 1 1
2 10 3 84 1
2 10 1 7 2
2 91 2 51 3
1 24 3 1 8
1 16 1 2 5
2 91 2 71 1
2 8 1 5 3
1 98 1 1 8
2 51 2 69 2
2 28 3 56 2
2 22 3 10 2
1 76 1 3 2
1 84 3 3 3
2 93 2 38 1
2 8 2 17 2
1 8 1 3 5
2 10 1 84 1
2 57 2 20 1
2 83 1 8 1
1 100 1 3 3
2 71 3 83 2
1 31 2 3 4
2 12 3 22 3
2 30 3 67 2
1 69 3 2 1
1 32 1 2 8
2 50 1 100 3
2 47 2 5 2
2 67 2 55 2
2 56 2 74 3
1 9 1 2 9
2 1 1 54 2
1 71 2 3 2
2 58 1 30 3
1 88 2 3 5
1 68 3 3 9
2 29 1 57 1
1 19 1 1 3
1 21 3 3 6
1 71 3 1 2
2 33 3 63 2
1 37 2 2 5
1 37 3 3 5
1 26 3 3 2
2 78 3 74 1
2 6 1 78 3
1 85 1 1 8
1 91 3 3 2
1 70 3 3 7
1 30 3 1 7
1 91 3 3 2
1 48 2 2 4
2 46 3 4 3
1 44 2 1 2
2 67 1 7 3
2 27 1 8 3
1 78 3 3 3
1 92 1 3 3
1 71 3 2 8
1 14 3 2 10
2 88 3 90 2
1 29 2 2 6
2 95 3 26 1
1 79 2 1 9
1 25 1 2 3
2 19 1 36 2
2 83 2 40 2
1 39 2 1 8
2 91 1 63 3
2 39 2 12 2
1 5 1 2 5
2 9 1 89 2
2 44 3 40 3
2 100 3 94 2
2 38 2 100 1
2 97 3 32 1
2 65 3 2 1
1 77 3 2 3
1 3 3 2 4
1 17 1 3 3
2 29 1 53 1
1 74 3 2 2
2 81 3 78 3
1 42 3 3 9
1 82 2 2 5
1 27 3 3 1
2 61 1 98 2
1 80 2 1 10
1 22 1 2 9
2 89 3 73 3
1 92 3 2 3
1 47 1 3 5
2 59 1 40 1
1 33 1 3 9
1 52 1 2 5
2 51 1 86 1
2 74 3 18 2
1 81 3 2 6
1 54 3 3 1
2 43 2 48 2
1 38 2 2 4
2 18 2 55 2
1 92 1 1 1
2 73 1 9 1
1 97 3 2 10
1 69 3 2 7
1 68 3 3 9
1 69 1 3 1
1 93 3 3 2
1 32 1 2 8
1 90 3 1 6
2 54 3 26 1
1 13 1 1 6
1 56 3 1 4
1 86 1 2 9
1 43 1 1 3
1 6 1 1 4
2 55 3 17 1
1 91 3 3 3
2 59 1 41 1
2 1 3 54 2
1 84 3 1 4
1 12 1 3 5
2 60 1 96 1
1 12 1 1 5
2 84 2 81 1
2 78 1 77 1
2 83 3 42 1
1 33 2 3 10
1 88 3 3 2
2 18 3 71 3
1 37 3 2 4
2 15 2 21 3
2 33 2 92 1
2 58 2 25 1
2 100 3 51 2
1 34 3 2 3
1 26 1 3 6
2 31 2 26 1
1 73 2 2 2
2 27 3 76 1
2 56 1 21 1
1 62 1 2 6
1 15 2 2 5
2 61 1 68 2
2 54 1 53 2
2 53 3 6 2
1 60 1 2 4
1 54 1 2 8
2 30 2 13 1
1 95 2 1 8
2 96 3 18 2
2 93 3 61 2
1 57 1 2 8
2 31 3 23 3
2 92 2 28 3
2 54 2 59 3
2 69 1 11 2
2 40 1 33 3
1 88 3 1 3
2 95 1 7 2
1 16 2 2 6
1 82 3 3 2
2 91 1 97 1
2 34 1 46 3
1 19 2 2 7
1 76 1 2 2
1 46 1 1 5
1 41 3 2 5
2 49 2 9 3
1 31 2 2 1
1 6 2 1 4
2 24 1 25 2
2 86 2 56 2
2 64 1 70 3
2 8 3 60 3
2 54 2 73 2
1 53 3 2 9
1 63 1 3 5
2 93 1 9 2
1 91 3 3 2
1 25 2 2 3
2 49 2 40 2
1 51 3 1 6
1 90 2 3 8
1 17 2 1 8
2 84 2 64 1
1 74 2 1 1
2 92 1 10 2
2 91 2 77 1
2 15 1 98 1
1 6 2 2 3
2 2 2 38 1
2 51 3 80 3
1 86 1 1 10
2 35 3 83 3
1 17 3 3 7
1 42 1 2 6
2 73 3 92 3
2 86 2 61 2
1 24 2 2 5
2 87 3 1 2
1 98 2 1 2
2 11 3 28 2
2 87 2 28 3
2 65 1 52 2
2 77 1 74 2
1 66 1 1 9
1 43 3 1 8
2 91 2 7 3
2 81 2 44 1
2 63 1 27 1
2 93 3 8 3
1 50 3 1 10
2 62 3 1 2
2 26 1 80 1
2 55 2 46 1
2 70 2 88 1
2 36 2 10 1
2 39 2 26 3
1 21 3 3 4
1 14 2 3 10
2 86 3 94 3
2 2 1 46 3
1 51 3 2 10
1 50 2 3 2
2 84 2 41 3
2 23 3 8 1
2 97 1 95 3
1 16 2 1 6
1 63 1 1 7
1 19 1 3 3
1 98 3 1 5
1 59 2 1 3
1 21 2 3 9
2 27 1 87 3
2 9 3 83 1
2 19 2 60 3
1 75 1 3 8
1 31 3 2 7
1 59 3 3 2
2 27 1 14 2
1 73 3 3 10
2 45 2 67 2
2 24 3 78 3
2 41 2 6 2
2 87 3 69 2
1 57 2 2 8
1 68 3 3 4
2 77 3 58 1
2 59 3 86 3
2 99 2 46 3
2 75 1 45 3
1 52 1 2 5
1 72 1 1 7
2 58 1 43 3
2 23 1 4 1
2 94 3 80 3
2 91 1 49 1
1 83 2 2 8
2 30 2 96 3
2 13 1 33 2
1 24 2 1 8
2 88 1 56 3
2 76 3 34 3
2 53 2 10 2
1 92 3 2 6
1 80 1 3 9
1 70 3 2 2
2 57 3 58 1
1 53 3 3 8
2 29 3 7 3
2 68 1 7 2
2 48 2 49 1
1 17 3 2 5
2 87 3 38 1
1 20 3 2 3
2 3 3 97 1
2 55 2 19 1
2 47 2 94 2
2 65 2 23 2
2 54 2 50 1
2 3 2 42 2
1 62 1 1 2
2 100 2 88 3
2 48 3 92 3
1 79 3 1 5
2 40 3 32 1
1 46 1 1 2
1 36 3 3 10
1 65 2 1 4
1 50 1 1 9
1 80 1 1 3
2 48 2 44 1
2 88 3 96 1
2 92 1 12 1
2 38 3 17 2
1 3 1 1 6
1 68 3 3 2
1 62 1 2 3
1 91 1 3 6
2 89 2 80 2
2 90 2 68 2
2 17 3 56 2
1 77 2 2 6
2 81 2 38 2
2 27 1 12 3
2 27 1 49 3
1 49 1 2 5
2 54 1 83 3
1 91 2 2 10
1 3 3 1 5
1 79 1 3 8
2 47 1 62 2
2 20 1 24 3
1 47 2 2 4
1 96 3 2 7
2 25 1 83 3
2 34 1 86 3
1 82 2 1 1
2 33 2 87 3
1 99 2 2 10
1 33 1 2 1
1 44 2 3 3
1 42 2 2 1
2 67 1 33 2
2 38 1 21 2
1 66 3 3 1
2 12 1 63 2
2 90 2 44 1
1 48 2 2 1
0.166485
0.145035
0.254213
0.245830
0.268149
0.207964
0.079499
0.127157
0.233007
0.132527
0.209874
0.196604
0.201677
0.071314
0.212058
0.178609
0.178092
0.188865
0.251975
0.120610
0.070614
0.186358
0.259718
0.151202
0.098715
0.167909
0.166435
0.128221
0.306995
0.200882
0.193683
0.246635
0.137606
0.196212
0.249841
0.228309
0.206846
0.259677
0.303300
0.147418
0.307186
0.154761
0.271292
0.312877
0.304700
0.187404
0.131512
0.166085
0.143717
0.169194
0.092177
0.174330
0.205403
0.288773
0.241365
0.171551
0.159429
0.165100
0.161702
0.208083
0.223135
0.263387
0.232543
0.227559
0.156374
0.128719
0.208088
0.116723
0.272981
0.123721
0.254747
0.109554
0.157147
0.134850
0.198889
0.141687
0.264043
0.233554
0.293792
0.126594
0.100913
0.207647
0.241278
0.486679
0.177541
0.252083
0.202006
0.258531
0.149585
0.172270
0.245304
0.174270
0.131063
0.239021
0.263349
0.203489
0.305582
0.125568
0.303334
0.244586
0.259720
0.346744
0.171620
0.278153
0.124279
0.132213
0.282387
0.161231
0.149149
0.113138
0.261860
0.082354
0.204112
0.121583
0.109798
0.364259
0.275128
0.274472
0.305262
0.266299
0.140532
0.242761
0.124756
0.194071
0.204174
0.235792
0.171138
0.135776
0.180659
0.159056
0.186380
0.341675
0.267736
0.319806
0.209198
0.196329
0.216288
0.159036
0.158124
0.152551
0.231357
0.108039
0.209114
0.277995
0.135819
0.338419
0.144462
0.144665
0.099518
0.123406
0.224415
0.226983
0.253564
0.190158
0.163218
0.266929
0.170044
0.243843
0.513149
0.159186
0.352119
0.166533
0.165335
0.166611
0.286013
0.166833
0.282404
0.318570
0.194809
0.118788
0.266354
0.145883
0.170218
0.151689
0.162983
0.284440
0.290898
0.263336
0.125525
0.182289
0.182010
0.134294
0.197925
0.318346
0.101839
0.205509
0.154347
0.088061
0.224492
0.203877
0.217726
0.130415
0.149264
0.258819
0.215656
0.131219
0.060791
0.180598
0.131774
0.100319
0.061244
0.184493
0.212277
0.271758
0.280351
0.119624
0.150239
0.404143
0.237470
0.250806
0.281043
0.202934
0.253534
0.090265
0.220048
0.130905
0.213031
0.174664
0.187302
0.171389
0.056596
0.201661
0.295572
0.131106
0.101241
0.257090
0.195776
0.218921
0.190958
0.173670
0.147358
0.158709
0.209922
0.209096
0.268895
0.462235
0.198735
0.183512
0.161628
0.351743
0.278814
0.172878
0.150688
0.089747
0.139854
0.191593
0.293729
0.263647
0.295533
0.172423
0.229366
0.245853
0.231653
0.124026
0.192223
0.102272
0.172781
0.273936
0.292347
0.291550
0.219853
0.172880
0.300610
0.253859
0.209206
0.239509
0.250048
0.211092
0.216213
0.259309
0.175533
0.180586
0.185337
0.173291
0.188081
0.302142
0.163326
0.168826
0.073360
0.141128
0.034655
0.442950
0.391701
0.202333
0.386597
0.084200
0.301071
0.204525
0.309761
0.050766
0.203605
0.124820
0.281156
0.141401
0.210272
0.172617
0.102813
0.210902
0.162866
0.215535
0.204608
0.258468
0.225578
0.289352
0.210272
0.135582
0.289351
0.192357
0.186748
0.204288
0.198946
0.347895
0.184919
0.216870
0.413225
0.258835
0.268405
0.158641
0.200215
0.139972
0.206329
0.129451
0.183609
0.068684
0.137463
0.205937
0.202271
0.178304
0.221533
0.230431
0.303807
0.100912
0.187763
0.279229
0.219091
0.325576
0.184928
0.257180
0.151886
0.330276
0.146228
0.052917
0.217813
0.248596
0.225664
0.211724
0.246111
0.197878
0.032830
0.308105
0.201035
0.218510
0.159955
0.250954
0.220371
0.150659
0.195316
0.412078
0.266342
0.353870
0.292628
0.199291
0.033518
0.169051
0.254808
0.109932
0.267122
0.196098
0.129568
0.123449
0.152320
0.194396
0.212451
0.108570
0.324320
0.112777
0.322464
0.167277
0.062856
0.106397
0.251013
0.165583
0.249394
0.130299
0.268009
0.258967
0.240185
0.174984
0.220527
0.070114
0.225761
0.142295
0.155388
0.240246
0.175688
0.204419
0.136144
0.108186
0.323637
0.244513
0.240644
0.108636
0.152654
0.363775
0.231769
0.498518
0.111346
0.226558
0.224003
0.197040
0.204301
0.273768
0.286428
0.188837
0.186831
0.162293
0.270242
0.248962
0.307324
0.226402
0.261581
0.058665
0.309088
0.150807
0.270853
0.183463
0.255197
0.262685
0.264497
0.249978
0.160477
0.136042
0.291131
0.210307
0.168453
0.186060
0.256530
0.343534
0.208538
0.127436
0.202582
0.193567
0.102450
0.142968
0.266558
0.208165
0.140837
0.330321
0.146745
0.130853
0.197696
0.232652
0.198578
0.173566
0.120576
0.210362
0.244739
0.503851
0.182786
0.105646
0.181024
0.188694
0.262018
0.205512
0.115408
0.229710
0.218856
0.260325
0.167982
0.203913
0.206747
0.286481
0.074139
0.173456
0.217187
0.113532
0.176725
0.148318
0.186326
0.210784
0.218850
0.145584
0.199699
0.315880
0.321359
0.179960
0.255132
0.133978
0.167206
0.262659
0.266924
0.143184
0.122101
0.235255
0.171536
0.135040
0.231817
0.257362
0.281114
0.184793
0.179047
0.118907
0.175527
0.244514
0.174491
0.158859
0.178029
0.212513
0.081792
0.197675
0.045184
0.290109
0.280698
0.201024
0.232031
0.385938
0.217244
0.057452
0.191857
0.253467
0.212064
0.171462
0.094536
0.264941
0.313184
0.161439
0.139579
0.204831
0.183423
0.220766
0.331502
0.243284
0.201827
0.139739