#1842. 基础 01 练习题
基础 01 练习题
基础 01 练习题
题目描述
标题: 基础 01 练习题 - Problem - QOJ.ac
#9465. 基础 01 练习题
对于一个 n×m 的 01 矩阵 A(下标从 1 开始,下同),定义一个 n×m 的 01 矩阵 B 是好的当且仅当:
-
对于第 i(1≤i≤n) 行,不存在 1≤j,k≤m,j≠k 同时满足:
Ai,j=Bi,k=1,Ai,k=Bi,j=0
-
对于第 i(1≤i≤m) 列,不存在 1≤j,k≤n,j≠k 同时满足:
Aj,i=Bj,i=1,Ak,i=Bk,i=0
初始 B 矩阵所有位置为 0,每次可以选择若干个位置,将它们同时变成 1。要求做完操作后,矩阵 B 仍然是好的。设最多执行 k 次操作,则矩阵 A 的权值为 k。
小 █ 现在有一个 N×N 的 01 矩阵 M。由于 N 很大,所以 M 由特殊方式生成。
初始 M 中所有位置均为 0,有 Q 次修改操作。每次操作给定 x1,x2,y1,y2,对于满足 x1≤i≤x2 且 y1≤j≤y2 的所有位置 (i,j),将 Mi,j 变为 1−Mi,j。
定义 Si,j 为 M 前 i 行前 j 列构成的子矩阵的权值。
输入格式
第一行三个数 N,Q,op。
接下来 Q 行,每行四个数 x1,x2,y1,y2。
输出格式
若 op=0,输出一个数 SN,N。
若 op=1,输出一行 N 个数,分别是 SN,1,SN,2,⋯,SN,N。
输入输出样例
样例输入 1
2 2 1
1 1 1 1
2 2 2 2
样例输出 1
2 1
样例 2 & 3
详见下发文件。
数据范围
Subtask 编号 分值 N≤ 特殊性质 1 5 4 A 2 10 50 3 10 5000 4 10 无 5 15 2×105 B 6 15 A 7 35 无
- 特殊性质 A:保证 op=0。
- 特殊性质 B:一次操作的代价为 (x2−x1+1)×(y2−y1+1),所有操作的代价之和 ≤2×106。
对于所有数据,保证:
1≤N,Q≤2×105,1≤x1≤x2≤N,1≤y1≤y2≤N,op∈{0,1}
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
50 100 1
29 40 15 35
38 45 18 22
1 2 10 28
4 15 16 21
35 39 46 47
22 36 4 7
7 43 8 19
16 22 1 43
14 42 41 48
23 40 40 41
29 39 2 44
8 38 9 13
21 22 32 43
35 46 15 15
41 47 1 41
1 30 12 28
6 26 18 46
31 37 16 19
2 47 15 29
21 36 43 44
17 20 15 31
3 44 35 46
25 35 11 39
7 18 35 50
24 39 6 38
14 31 3 35
1 37 41 43
25 46 33 39
20 33 7 8
2 15 19 32
39 50 16 26
27 29 2 36
14 15 29 46
20 50 46 48
4 31 48 50
29 49 5 28
35 40 20 35
18 18 41 42
15 27 15 41
6 32 3 22
35 41 29 39
19 24 29 37
9 46 17 35
17 39 17 24
7 32 6 13
1 3 8 43
35 50 10 17
26 37 45 48
19 24 33 41
30 45 33 42
3 12 23 48
2 22 37 45
47 47 47 49
20 27 17 37
28 30 36 39
9 19 1 44
30 32 5 35
12 23 15 38
35 50 13 17
32 48 1 31
3 45 17 47
6 22 7 24
8 21 19 41
24 33 25 41
2 42 15 26
17 17 11 46
22 35 7 21
44 45 42 48
1 42 11 49
6 45 7 43
10 17 7 22
17 42 7 27
16 30 1 19
23 38 15 21
23 46 44 45
20 46 14 21
32 34 23 46
15 19 18 28
25 28 7 24
8 36 43 43
15 42 36 39
8 15 1 50
7 24 10 38
15 21 43 43
10 12 36 37
6 46 19 29
16 22 25 36
10 21 2 18
16 47 6 49
7 36 8 45
11 29 8 28
23 36 13 50
34 38 40 46
6 26 15 45
9 23 13 20
1 23 14 25
15 15 32 46
5 41 34 41
2 31 6 32
19 34 6 29
50 53 67 65 31 13 15 9 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
样例 2
200 1000 1
61 144 85 181
5 156 70 108
94 119 144 156
56 147 128 142
40 102 83 157
9 131 40 152
154 165 7 99
18 48 133 172
78 85 99 161
144 148 87 123
131 144 17 174
10 42 46 159
60 169 19 23
42 74 153 188
75 176 111 176
16 45 11 50
66 158 139 190
55 134 154 163
146 189 43 148
118 154 20 82
25 185 68 113
46 72 70 122
34 115 39 82
5 96 60 158
98 178 160 173
47 172 83 165
47 153 61 115
3 194 96 183
73 94 24 169
115 187 188 196
16 37 149 195
16 164 32 101
57 174 151 192
51 134 17 160
5 132 74 90
1 175 13 133
147 154 64 191
154 179 95 166
106 157 144 196
49 105 182 199
91 195 24 185
23 133 70 93
41 163 81 184
22 40 38 191
102 145 79 167
47 79 92 109
136 200 73 77
7 200 127 130
11 114 149 157
73 133 35 196
142 197 82 119
84 140 65 77
74 190 20 113
126 146 29 162
66 129 4 100
195 200 59 162
23 30 41 60
11 78 52 68
1 160 80 94
33 105 139 194
6 6 56 62
13 126 111 146
18 63 47 169
141 151 25 175
79 114 25 174
74 113 55 148
4 23 184 186
54 165 27 99
97 172 39 85
37 127 23 113
14 55 111 162
55 57 80 136
59 93 3 158
79 195 10 174
134 144 126 150
76 192 61 64
61 115 43 180
70 77 104 186
6 9 115 139
83 182 165 196
144 160 67 110
119 188 9 38
18 56 66 87
41 177 149 171
81 155 129 154
36 122 103 143
141 154 4 88
144 170 16 189
41 106 127 199
11 149 80 140
119 139 12 95
25 109 75 78
157 184 39 195
5 6 22 165
25 95 78 174
26 199 30 175
110 189 71 123
2 137 65 139
32 182 31 134
35 62 154 161
171 175 64 79
13 194 55 101
28 50 17 196
1 15 96 154
118 126 71 189
32 178 47 174
125 145 33 150
46 50 17 83
53 142 163 197
15 104 53 56
71 159 181 196
3 154 10 124
28 79 74 96
7 135 52 92
104 133 25 118
140 165 89 158
135 173 44 100
20 180 87 142
15 70 35 109
14 121 35 91
6 52 74 93
47 155 5 48
49 111 106 197
22 124 22 155
1 18 175 180
101 125 63 132
119 170 56 79
60 85 30 117
144 186 167 171
44 73 46 185
123 180 151 181
136 177 120 167
12 155 12 108
14 25 26 99
167 193 9 70
28 50 24 177
30 124 8 23
98 199 83 145
41 195 16 95
19 87 68 95
20 176 194 195
7 126 27 137
5 69 11 44
96 120 62 152
108 123 130 196
24 110 104 156
75 143 168 187
8 98 152 176
6 75 158 159
104 124 72 85
81 116 132 168
79 87 72 172
24 90 167 181
93 176 61 164
110 176 103 121
119 185 138 196
54 113 179 188
35 46 91 141
4 40 29 120
21 29 20 175
9 190 8 172
84 118 35 97
20 148 4 195
29 41 123 200
111 181 6 80
23 93 139 149
165 189 84 113
76 180 81 96
134 151 50 119
46 131 130 197
132 159 125 196
58 79 14 67
7 72 13 105
67 171 72 88
24 100 43 46
13 164 54 91
60 93 132 178
5 80 71 127
162 169 109 153
172 193 25 191
77 154 24 117
124 124 96 167
61 99 136 178
4 30 21 183
74 96 86 105
85 107 64 120
62 126 125 182
111 130 15 77
149 175 57 138
177 198 6 48
24 33 14 101
50 166 102 159
10 73 154 155
83 177 123 162
25 104 112 144
66 189 27 73
63 144 34 122
39 166 34 189
167 178 101 197
11 74 37 176
26 150 45 160
127 133 121 173
2 160 56 176
35 136 99 131
20 163 38 174
60 91 36 101
70 117 21 178
89 148 26 104
31 137 46 188
22 44 44 161
16 162 73 77
54 68 28 88
45 62 21 111
42 43 100 114
124 140 26 62
124 141 90 185
1 68 90 115
23 71 91 200
50 176 28 180
85 117 10 40
39 172 31 197
23 109 32 177
62 62 22 39
24 186 19 65
83 131 77 178
100 159 66 117
98 130 148 156
119 144 65 135
31 41 2 37
50 52 144 166
6 14 12 154
20 120 91 199
8 160 80 160
72 74 178 197
95 112 10 145
36 182 5 127
125 141 62 85
95 101 88 188
91 172 6 116
127 180 78 109
61 97 66 149
110 197 38 92
75 135 136 196
92 135 5 182
40 177 19 26
120 132 72 171
36 147 110 196
13 101 72 185
58 133 19 87
8 72 4 84
124 162 74 91
48 159 64 100
116 146 6 41
44 176 129 146
13 195 30 149
51 148 87 169
57 195 41 47
154 182 31 103
119 191 76 97
80 196 34 61
6 43 90 182
150 165 41 162
88 177 78 99
133 163 74 97
125 187 30 110
26 144 82 144
82 194 136 199
85 136 132 160
86 131 49 125
106 111 139 156
121 156 4 140
40 129 70 85
58 181 14 192
7 64 86 104
38 130 51 84
3 44 59 110
146 181 51 111
106 151 103 112
88 182 156 161
124 170 2 190
60 89 159 173
2 121 62 75
21 94 100 151
143 149 6 40
87 118 60 93
84 199 160 171
70 132 34 74
135 151 37 135
115 135 63 148
78 168 85 146
159 160 3 195
120 183 89 136
3 74 71 179
35 154 66 161
106 165 10 116
30 117 58 141
100 125 56 60
90 183 126 175
153 188 69 132
53 112 61 133
78 150 30 180
91 190 26 158
37 182 24 169
91 173 48 70
95 142 23 164
5 137 23 122
162 182 32 147
57 186 127 158
98 100 48 103
144 157 52 124
111 132 23 126
117 128 26 122
150 157 66 169
89 177 118 163
134 154 24 163
2 134 64 148
11 92 69 112
121 191 63 71
168 196 41 72
51 183 77 128
5 52 9 179
60 115 26 66
42 181 5 157
137 150 145 165
31 146 98 200
58 148 4 100
17 62 41 56
12 141 52 174
29 114 167 169
164 168 44 116
97 125 62 116
10 170 46 76
55 167 41 111
129 165 24 29
42 50 90 120
50 102 166 194
87 196 195 200
87 125 4 189
34 152 87 99
25 197 126 146
47 164 97 186
127 184 110 137
34 103 145 200
4 36 87 129
54 102 10 90
9 97 167 196
39 129 66 190
117 154 70 90
38 78 15 64
18 40 112 198
101 174 29 30
53 72 61 95
49 70 127 181
58 76 77 86
27 64 22 63
133 137 68 175
4 103 6 200
86 120 66 137
81 107 51 109
57 171 92 183
123 194 51 65
108 127 50 62
47 141 162 185
25 112 150 199
4 102 19 163
45 90 9 151
32 183 150 151
93 124 72 91
93 186 44 111
80 191 86 174
128 186 131 187
52 151 89 170
125 168 132 161
11 136 64 141
56 111 63 70
11 106 135 187
116 141 109 172
8 67 173 187
141 172 142 182
34 55 142 142
72 88 79 162
6 46 46 61
156 172 50 180
57 71 78 175
74 94 2 107
43 145 89 161
62 200 73 99
52 163 5 144
43 106 40 167
10 118 108 188
93 94 183 192
87 106 94 197
62 146 2 28
58 192 37 93
175 176 10 127
35 140 5 70
18 100 67 80
8 40 13 163
98 120 83 83
6 112 154 168
56 194 124 189
7 88 71 143
104 168 33 146
151 186 72 112
130 173 149 162
78 145 94 171
19 199 49 92
24 37 43 196
8 124 106 151
80 86 134 154
36 112 56 190
42 63 37 78
32 188 82 121
44 75 66 119
33 81 84 167
67 70 5 113
143 180 176 183
65 68 149 150
50 182 106 143
156 183 21 131
149 151 3 44
86 114 128 143
57 182 58 107
177 197 39 56
6 114 77 130
177 178 75 136
41 199 98 130
190 191 32 191
31 67 1 131
22 159 4 118
39 161 125 197
111 115 13 77
32 185 109 191
58 196 24 132
113 180 8 154
153 194 22 63
21 23 109 140
17 162 77 187
16 182 144 165
74 116 30 179
1 173 149 182
88 169 130 166
94 106 114 189
39 169 51 192
1 114 23 195
10 162 148 182
23 188 82 145
135 188 76 131
21 138 50 158
83 199 68 94
1 72 107 122
33 137 71 85
50 171 88 120
168 181 46 85
15 16 35 52
7 100 79 185
18 191 115 192
163 189 90 122
13 181 14 152
38 131 76 91
161 188 15 140
118 197 6 123
27 121 28 194
99 130 19 105
77 102 146 151
103 175 5 190
6 111 4 66
153 159 42 152
50 95 116 162
122 123 172 177
174 177 157 170
15 51 14 173
32 126 12 82
106 127 21 50
41 85 64 130
48 67 1 152
23 106 53 127
2 56 114 118
28 80 41 54
82 184 115 196
5 31 54 155
90 178 8 195
26 133 110 119
24 61 172 192
48 118 20 154
128 177 125 155
54 191 26 84
44 112 59 190
122 191 156 161
64 136 131 158
42 143 5 46
31 156 70 119
9 83 55 102
44 102 82 97
40 101 9 165
130 195 11 81
62 126 90 152
27 178 81 115
77 124 105 144
7 77 3 104
4 139 127 154
56 70 34 80
17 158 18 82
144 150 52 76
7 42 52 163
75 166 57 108
109 193 5 161
14 115 126 126
90 113 6 98
188 198 76 183
30 46 166 173
86 124 177 190
32 138 20 153
124 134 70 180
33 186 14 77
46 53 114 130
137 138 125 177
170 188 13 36
22 160 95 141
185 190 51 103
61 118 113 154
34 72 1 34
81 122 49 99
46 180 64 72
16 112 60 200
34 58 72 112
35 37 185 194
42 68 178 178
46 195 47 96
115 190 100 102
48 147 27 29
49 164 142 148
67 170 23 171
165 177 103 131
114 197 46 101
62 120 64 90
98 138 35 99
165 171 28 111
56 166 57 133
5 110 71 91
79 83 48 121
43 106 43 68
22 124 71 165
88 113 24 31
87 114 89 192
70 86 21 72
58 83 2 90
84 127 54 76
12 26 51 136
178 179 32 91
29 46 34 90
1 157 110 178
23 91 39 175
173 196 97 145
43 44 66 168
2 97 26 26
54 173 83 92
37 156 21 104
140 143 27 145
15 19 64 182
37 97 24 37
47 124 48 176
76 133 49 78
45 49 11 164
21 70 63 144
153 175 113 163
194 196 191 197
42 199 1 89
22 109 113 145
86 129 91 196
16 43 190 197
122 150 64 158
11 23 10 23
42 114 143 148
152 171 82 198
130 130 109 156
44 176 39 139
57 109 26 42
176 192 157 185
90 143 89 169
137 169 36 69
60 99 1 13
90 119 135 157
25 59 36 57
5 8 3 13
90 148 42 93
4 175 159 196
56 151 114 153
11 52 14 171
133 185 150 157
14 37 5 70
71 121 154 188
20 195 56 154
48 108 42 84
87 160 21 170
71 89 3 167
38 164 19 52
175 184 41 63
56 164 138 167
99 142 46 88
138 179 69 90
142 176 7 190
3 30 64 108
33 140 29 164
65 135 188 198
37 175 19 52
164 176 9 188
117 121 91 190
132 186 101 104
15 155 98 128
23 75 47 181
68 102 14 35
19 48 2 109
127 192 75 195
51 128 28 140
13 73 32 176
113 158 9 112
9 161 13 88
33 45 58 126
90 149 27 97
108 200 113 144
68 103 17 68
46 127 9 198
31 129 76 102
90 199 41 151
101 109 8 189
173 186 40 125
70 164 2 28
15 20 3 198
60 126 74 107
92 130 63 188
166 179 68 79
164 171 63 98
31 34 84 97
73 107 35 142
8 187 44 187
33 173 170 188
82 110 16 29
138 142 66 134
26 85 116 188
162 188 91 187
86 170 3 40
46 188 36 193
46 118 45 180
93 189 32 183
94 129 51 150
154 189 11 145
17 185 98 188
57 61 83 171
70 84 23 124
3 130 70 72
120 132 9 43
38 104 91 94
29 157 41 118
51 104 57 100
37 165 60 160
32 124 107 124
98 137 87 194
109 120 130 188
27 64 119 133
64 120 68 174
139 153 6 42
108 142 48 136
57 138 15 60
6 192 70 77
12 63 18 152
6 108 67 194
97 187 60 89
4 85 155 187
176 199 39 162
122 133 117 156
105 149 15 35
48 62 42 108
105 114 52 130
63 107 10 37
106 149 114 148
153 187 90 101
3 71 19 77
142 147 84 171
7 187 16 100
4 129 22 66
79 185 96 125
19 155 50 87
1 92 12 187
75 174 158 191
10 56 30 184
105 138 53 124
76 188 164 173
2 156 18 147
101 119 25 164
147 149 2 159
160 199 95 143
31 90 57 76
25 184 58 175
115 185 163 180
137 155 127 153
39 176 20 77
1 141 124 133
18 112 57 129
105 121 29 172
59 184 66 177
37 77 21 38
123 157 55 149
15 149 84 197
90 142 1 51
29 151 85 153
86 95 8 178
31 151 110 116
10 26 49 135
167 188 78 167
113 184 124 163
67 180 117 144
58 99 175 180
66 133 38 108
73 155 136 149
9 70 70 193
52 159 75 174
64 189 86 182
74 193 82 159
88 150 97 195
68 183 26 81
69 98 12 174
53 70 85 85
8 187 97 120
12 53 112 133
50 187 77 180
41 76 59 114
63 182 16 154
5 157 75 187
80 167 124 131
89 149 45 168
64 130 103 151
3 20 11 48
47 77 18 158
32 55 86 117
81 88 2 166
11 118 6 127
12 64 15 151
145 172 29 112
1 100 12 59
178 180 7 89
101 172 132 168
33 109 160 166
26 164 151 155
58 153 37 141
37 134 27 184
29 146 135 150
7 159 85 164
104 115 24 29
5 194 105 118
71 166 63 158
135 188 22 65
105 171 36 62
141 165 31 185
62 67 41 57
119 146 92 149
25 96 22 30
67 158 39 187
128 157 90 128
32 42 6 134
16 157 24 61
171 183 26 127
15 16 47 71
100 101 63 132
18 186 125 166
90 101 26 159
101 117 92 186
5 18 131 172
137 179 187 200
130 168 26 72
42 130 122 195
94 136 132 182
194 199 63 73
72 147 21 178
45 107 37 84
43 108 20 183
78 114 112 151
65 112 16 127
60 149 21 195
138 156 51 153
59 104 181 197
10 25 14 166
46 134 86 149
43 135 32 76
82 146 116 122
49 84 76 133
79 122 19 73
64 133 159 181
22 183 144 174
145 165 15 123
45 121 178 181
73 130 53 130
60 99 11 66
111 187 47 157
110 166 17 95
99 103 120 171
42 141 11 152
13 143 50 166
144 146 28 180
150 199 5 149
45 200 99 153
80 142 93 182
55 57 29 137
47 118 82 156
134 150 93 199
21 33 15 44
168 198 135 137
41 133 40 101
142 170 72 89
29 102 27 61
130 176 107 170
51 142 46 191
117 199 96 192
13 147 104 156
6 93 54 145
29 149 124 140
61 120 148 193
32 34 5 57
114 115 36 110
194 199 123 158
97 178 76 187
87 158 44 53
63 142 134 191
16 194 37 109
33 129 19 64
165 169 55 135
130 131 62 72
96 145 46 155
91 185 93 113
98 189 29 63
87 114 112 143
100 145 29 69
79 154 131 167
19 28 70 192
110 190 74 182
138 176 77 144
66 84 152 161
30 157 67 128
17 174 61 87
172 173 16 87
15 15 67 122
32 196 160 175
71 159 164 178
26 184 32 86
47 189 97 111
50 160 108 150
111 153 167 180
55 116 63 141
152 176 85 198
19 172 151 155
23 124 18 153
29 127 74 117
85 182 3 183
79 88 103 154
49 160 45 125
9 151 150 183
30 154 11 23
15 147 176 196
102 161 96 117
145 147 4 43
58 197 21 143
14 108 3 54
16 108 44 200
112 131 10 181
33 85 52 85
71 187 108 169
38 131 103 193
139 179 102 140
41 105 29 126
17 96 101 179
31 120 56 131
123 178 64 141
75 181 73 155
26 117 169 176
17 116 103 159
122 180 82 151
45 85 65 138
149 160 68 172
111 200 92 141
160 196 38 195
77 181 61 160
144 181 51 78
46 71 22 172
106 129 97 126
104 140 107 129
151 200 159 167
89 169 7 156
47 107 130 175
143 185 83 113
6 112 2 156
82 82 9 140
11 156 33 197
94 136 10 49
6 192 105 126
43 52 93 181
52 131 9 157
35 125 140 192
31 50 135 185
93 122 142 192
133 189 50 149
61 129 94 102
20 38 44 100
33 132 99 189
185 196 25 172
39 187 84 130
52 76 30 47
51 132 10 109
46 46 95 110
2 28 18 18
58 169 38 145
48 119 80 107
190 200 52 143
45 99 84 87
146 178 44 66
7 114 4 114
115 126 44 111
24 130 67 167
127 193 120 133
36 42 89 91
100 148 56 98
128 168 174 194
135 171 57 161
4 113 7 46
93 109 62 175
98 188 3 131
137 178 95 149
24 142 69 113
3 85 174 181
33 107 84 196
49 139 140 152
17 182 135 156
77 171 99 126
128 199 63 181
39 159 23 174
44 175 38 57
130 163 4 154
60 160 118 124
21 182 12 90
53 68 41 182
65 149 7 155
63 133 54 132
17 17 27 60
133 169 154 191
156 200 81 149
77 84 125 125
36 122 9 171
34 195 144 187
66 130 78 100
7 191 76 126
126 154 68 116
24 47 102 133
20 137 32 123
47 85 140 143
145 175 4 134
41 43 1 42
42 153 132 196
86 141 84 115
101 189 172 179
3 78 179 192
24 35 118 144
65 66 88 196
104 167 40 68
8 194 149 200
10 149 43 125
100 106 21 84
12 148 27 54
77 183 43 52
30 133 30 170
15 127 82 175
30 90 131 181
30 128 119 140
13 107 48 75
24 39 55 196
51 104 104 136
76 129 72 82
65 166 81 165
22 71 45 69
28 52 27 73
128 163 111 194
109 110 25 37
136 161 21 128
1 129 140 193
2 122 150 192
31 116 160 182
16 197 74 194
6 149 24 85
63 67 50 163
7 110 47 104
73 113 46 174
11 164 153 176
78 151 14 135
174 190 37 99
50 172 50 126
1 72 3 7
145 191 58 62
111 160 101 154
83 168 18 160
129 145 86 191
52 193 51 97
53 81 116 164
200 195 121 105 91 67 50 41 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1