题目描述
Problem
Monk lives in Otakuland. Otakuland consists of N vertices and N-1 directed edges. i-th edge is a directed edge either from i-th vertex to i+1-th vertex or from i+1-th vertex to i-th vertex.
You are given M Queries. Queries are 2 types:
1 l r - Reverse the direction of the edges between l-th vertex and r-th vertex.
2 f t - Output the minimum number of edges which you have to reverse the direction to arrive from f to t.
Input:
The first line contains two integers N, the number of vertices and M, the number of queries.
The next line will contains N-1 characters which represent the direction of the edges.
i-th character is either '>' or '<': '>' represents that only i -> i+1 is valid, '<' represents that only i+1 -> i is valid.
The following M lines will each contain a query like the ones mentioned above.
Output:
For query 2, print the answer in a new line.
Constraints:
2 ≤ N ≤ 200000
1 ≤ M ≤ 200000
1 ≤ l < r ≤ N
1 ≤ f , t ≤ N
SAMPLE INPUT
6 6
<<>
2 1 6
2 6 1
1 3 5
2 1 6
1 1 6
2 6 1
SAMPLE OUTPUT
2
3
0
0
Explanation
In the sample testcase the graph is like this, 1->2->3<-4<-5->6.
At the first query, Monk have to reverse the direction of 3rd edge and 4th edges to arrive from 1st vertex to 6th vertex.
Second, Monk have to reverse the direction of 1st, 2nd, and 5th edges to arrive from 6th vertex to 1st vertex.
Third, Reverse the direction of the edges between 3rd vertex and 5th vertex. After the query, graph is like this, 1->2->3->4->5->6.
Fourth, Monk don't have to reverse the direction of any edge.
Fifth, Reverse the direction of the edges between 1st vertex and 6th vertex. After the query, graph is like this, 1<-2<-3<-4<-5<-6.
Sixth, Monk don't have to reverse the direction of any edge.
输入格式
见题面
输出格式
见题面
样例输入
338 2940
>><<<<<><<>><>><<><<<<<<><<<>><>>>>><<<<<<<<<<>>><>>>><<>><<><<<>><>>><<>>><<<<>><>><<<><><<<>><<>><<>><><>><<<><><><<><><>>>>><><<><>><<<>><<>>>>><<><<<<>>>>>>>>><><<><><<<><<<>><><<<>><><<><<<><><><<><><<><>><>><<><<>>>><>>>>><><<><<<<<<><><<><>>><<><>><>><<<<>>><><>><><>>>><><><<>>><>><>>><<>>><><><>><><>>>><<<><><>>><<><<<><><<<><>
2 333 11
2 221 235
1 8 155
1 206 253
1 5 247
1 33 204
2 25 145
2 227 304
1 176 236
2 163 117
1 129 179
2 11 289
2 328 35
2 223 102
1 305 307
1 100 289
1 91 301
1 36 94
1 167 285
1 125 176
1 78 131
2 184 248
2 72 80
1 65 102
2 163 118
2 179 47
2 9 251
2 178 237
2 245 216
1 13 36
1 43 304
1 29 141
1 268 274
2 72 152
1 46 80
2 166 228
2 252 308
1 15 67
1 158 200
2 2 232
2 167 64
1 48 292
1 125 287
1 91 315
2 192 6
1 87 153
2 318 210
1 136 291
1 22 53
1 5 94
1 35 141
1 174 207
1 115 128
2 285 323
1 275 322
1 19 139
2 148 211
1 180 219
2 293 148
1 114 230
2 60 25
1 144 337
1 85 153
2 278 173
1 123 124
2 197 18
2 13 326
2 258 69
2 240 101
2 80 108
2 130 159
2 232 44
1 16 299
2 106 169
2 32 134
1 41 332
1 90 229
2 215 31
2 116 244
2 89 325
2 81 111
1 299 303
2 329 256
2 285 61
1 65 234
1 115 140
1 36 282
2 75 66
2 190 41
2 16 56
1 29 335
2 21 155
1 52 310
2 12 149
1 137 299
2 221 328
2 298 45
2 36 212
1 185 270
2 212 32
2 13 81
2 183 171
1 57 219
1 125 165
2 36 270
1 242 254
1 110 241
1 271 283
1 132 177
2 313 187
1 95 198
1 190 277
2 57 10
2 61 254
1 254 282
1 14 221
2 174 43
1 74 98
1 118 296
2 319 276
1 94 252
1 22 92
1 62 221
2 230 30
1 13 94
1 42 123
2 13 327
1 82 103
1 195 205
1 36 40
1 146 213
1 5 210
1 201 325
1 154 219
2 181 307
2 83 44
1 191 276
2 20 23
1 126 141
1 28 278
1 111 283
1 147 148
2 196 92
1 11 73
1 73 278
2 167 256
1 62 328
1 5 143
2 333 265
1 55 323
1 153 245
1 91 127
1 61 86
2 101 110
1 90 112
1 15 75
2 274 272
1 117 139
2 92 65
1 68 303
2 303 250
2 103 254
1 316 322
2 287 299
1 98 318
1 194 335
2 276 74
1 44 287
2 230 289
1 45 82
1 307 338
1 203 323
2 281 290
2 215 245
2 270 176
2 249 233
2 253 180
1 244 251
2 139 102
2 98 306
2 153 330
2 168 136
1 67 308
1 221 228
1 124 254
1 138 188
2 118 252
2 206 304
2 149 187
2 72 282
1 187 219
1 48 245
1 51 237
2 289 107
2 194 116
2 242 316
2 195 225
1 286 289
1 12 41
2 3 19
1 30 218
2 227 253
2 123 71
2 185 122
2 149 63
1 106 196
1 117 185
2 231 122
2 5 101
1 187 247
1 126 194
1 157 333
1 236 296
2 166 47
2 88 261
1 223 325
1 121 172
2 69 227
1 62 311
2 189 3
2 172 284
1 78 164
2 283 119
2 150 284
2 281 210
1 78 279
2 315 114
1 179 277
2 306 63
1 23 169
2 99 84
1 20 25
2 232 294
1 161 312
2 100 78
1 247 327
1 14 232
1 93 206
1 55 335
1 91 297
1 14 334
1 51 271
1 20 92
2 308 243
1 132 188
1 95 181
2 245 42
2 156 245
1 161 188
2 109 62
2 162 13
1 200 255
1 152 257
1 225 308
2 144 139
2 130 178
1 171 210
1 123 250
1 26 206
1 24 325
2 111 151
1 102 176
2 106 72
2 85 140
1 54 222
2 169 311
1 105 206
2 83 307
1 53 326
1 167 282
1 314 326
2 90 203
2 227 183
2 279 54
2 77 246
1 51 283
2 38 269
2 305 227
1 281 337
2 59 216
1 1 322
1 95 187
1 149 182
1 201 334
2 25 262
1 184 306
2 142 178
1 6 237
1 128 271
2 23 131
1 41 44
1 95 190
1 244 266
1 54 323
1 213 261
2 162 5
2 116 235
1 4 287
1 59 172
1 262 332
1 82 226
2 107 237
2 267 272
1 162 209
2 63 170
2 100 146
1 17 282
1 165 321
2 243 155
2 206 216
1 107 331
1 211 213
2 296 234
1 34 250
1 243 259
2 157 262
2 226 164
2 75 153
2 280 282
2 11 299
2 15 35
2 188 239
1 86 90
1 237 301
1 126 271
1 197 245
1 301 319
2 274 41
1 106 327
1 175 199
1 8 257
2 257 110
1 80 323
2 99 253
2 156 80
2 8 256
2 35 148
1 240 272
1 220 284
2 61 195
1 45 89
2 318 101
2 47 201
1 188 325
2 226 221
2 140 335
1 63 286
1 81 332
1 89 305
2 218 150
2 92 231
1 256 283
2 131 300
1 28 281
2 243 128
1 164 170
1 114 273
2 286 322
2 248 168
2 193 75
1 37 93
2 337 182
1 227 255
2 43 34
1 259 333
1 151 328
2 47 221
2 152 209
1 218 287
2 122 59
2 169 72
2 104 235
1 64 166
1 120 171
2 135 203
2 165 152
1 4 17
1 259 313
1 17 188
1 163 278
2 122 332
1 24 81
1 39 266
1 227 250
1 111 283
1 93 224
1 78 98
1 230 306
2 35 90
1 127 254
1 33 164
2 49 319
1 100 160
2 131 183
1 202 296
2 44 75
1 208 302
2 35 173
2 151 242
2 164 22
1 45 225
2 281 332
1 11 79
2 51 169
1 21 167
1 176 293
1 237 264
2 118 136
1 51 123
1 84 94
1 46 282
2 129 267
2 176 17
1 245 311
2 268 320
2 255 114
2 40 58
1 263 313
1 126 223
1 112 145
2 120 211
1 35 170
2 184 144
2 262 21
2 8 100
1 232 286
1 7 220
1 231 330
1 20 90
2 217 132
1 220 318
1 258 338
2 130 319
1 147 162
1 131 178
1 42 53
2 35 78
1 239 325
1 154 243
1 88 192
1 85 296
2 79 75
1 25 295
2 124 186
1 78 290
2 203 283
2 157 31
2 265 295
2 300 166
2 57 74
1 246 262
2 120 95
2 228 133
2 44 268
1 163 283
1 127 211
2 265 25
2 299 176
2 247 78
1 131 177
1 78 115
1 61 154
1 285 310
2 14 79
2 4 93
2 207 46
1 146 248
2 338 311
2 197 63
2 172 69
1 25 320
2 267 129
2 194 268
2 66 226
1 306 318
2 189 123
2 2 152
1 53 125
2 203 313
2 317 290
1 10 78
2 25 313
2 62 162
1 275 316
1 95 219
1 112 202
1 154 219
2 207 101
1 123 150
2 194 257
1 47 269
2 116 20
2 201 243
1 112 244
1 105 286
2 96 263
2 5 21
2 277 138
1 270 323
2 85 269
2 308 63
2 143 210
2 144 257
2 238 89
2 248 335
2 267 323
2 272 21
1 24 303
1 96 298
1 53 180
1 144 166
2 181 228
1 159 218
1 25 335
1 188 300
1 105 312
1 51 126
1 122 227
1 20 65
1 198 237
2 149 24
1 135 276
2 63 159
1 170 210
1 255 308
1 18 203
2 328 104
2 156 281
1 83 317
1 212 320
2 228 156
2 116 106
2 311 117
1 9 96
2 225 323
1 64 330
1 25 176
1 23 188
2 24 214
1 6 193
2 91 321
2 200 110
2 297 316
1 152 241
1 240 323
2 227 34
2 81 99
2 117 135
2 328 329
2 44 206
2 54 252
2 13 264
2 44 205
2 202 232
1 57 100
2 134 30
2 325 26
1 281 330
2 278 241
2 182 217
1 61 287
1 285 306
2 233 85
2 233 166
2 192 189
2 60 175
1 11 191
2 27 183
2 333 306
1 79 209
2 258 42
2 242 43
1 194 223
1 46 202
1 18 263
2 251 231
2 200 41
2 262 212
1 28 76
2 157 189
1 17 183
2 318 191
2 236 330
2 146 240
1 163 316
1 3 337
1 145 204
1 194 263
1 175 221
2 219 222
1 251 272
1 17 23
1 9 196
2 194 142
1 110 147
2 337 53
1 9 95
2 286 180
2 35 265
2 151 89
1 143 155
2 67 305
2 276 21
1 16 63
2 193 44
2 20 96
1 132 157
2 214 311
2 248 118
1 197 265
1 81 109
1 3 22
2 178 269
2 189 282
1 129 233
2 251 275
2 323 275
2 164 129
1 86 137
2 239 235
1 38 232
1 308 323
2 248 161
1 97 145
2 96 318
1 99 175
2 258 144
1 138 253
2 21 172
1 78 272
1 151 171
1 133 266
2 332 315
1 171 256
2 145 230
1 83 124
1 92 238
1 48 239
2 281 189
2 39 100
1 42 307
1 198 288
2 332 8
2 79 34
1 63 119
2 195 25
1 165 167
2 292 124
1 48 336
1 4 137
1 132 234
1 285 330
1 163 223
2 279 57
1 306 333
2 127 161
2 91 90
1 41 310
2 222 292
2 133 338
1 45 140
2 175 20
1 39 226
1 44 74
1 12 216
2 315 147
2 25 37
2 8 226
1 234 312
2 221 217
2 176 130
1 55 304
2 143 192
1 54 259
1 74 268
2 91 310
2 264 220
1 290 322
1 53 171
2 219 168
2 297 224
2 247 61
1 107 154
2 275 86
1 26 33
1 53 103
2 136 88
1 41 129
1 86 192
1 309 337
1 124 284
1 129 299
2 5 90
1 224 327
1 38 326
2 126 338
2 226 15
1 35 175
2 123 250
1 139 243
2 154 81
1 80 196
2 255 281
2 119 160
2 227 336
2 47 261
1 6 261
1 59 238
1 62 122
2 155 41
2 338 16
1 69 216
1 240 298
1 113 331
2 245 10
2 259 173
1 144 305
1 40 244
1 25 138
1 222 233
1 94 246
1 160 326
2 323 78
2 333 305
2 157 47
2 20 228
1 11 308
1 13 321
1 103 120
2 48 159
2 320 167
2 158 298
2 144 199
2 260 57
1 45 263
1 78 151
1 16 325
2 272 162
2 22 24
2 227 218
2 230 124
2 155 218
2 10 198
2 110 272
2 25 50
1 33 267
1 297 298
1 66 305
2 266 140
1 60 96
2 256 283
2 267 202
1 118 231
1 134 286
1 88 261
2 17 171
2 40 1
2 21 193
1 130 303
1 36 261
1 60 93
1 148 170
1 38 308
1 27 285
2 46 51
2 323 23
1 222 247
2 335 70
1 304 326
1 8 119
2 282 86
1 108 146
2 204 192
2 326 335
2 69 202
1 187 200
1 100 300
2 116 5
2 201 161
2 156 24
2 269 28
2 113 192
1 81 303
1 36 295
2 65 23
2 275 124
2 133 150
1 131 232
2 326 187
2 49 139
2 159 25
2 125 322
2 313 115
2 328 246
1 137 195
1 18 294
1 247 249
1 38 235
2 78 302
2 96 273
1 252 324
2 229 173
2 27 93
2 120 220
1 182 278
1 155 292
1 37 179
2 73 177
1 1 191
2 216 211
1 131 316
2 304 298
2 302 322
1 146 260
1 150 318
2 7 261
2 33 96
2 197 20
1 87 206
2 8 78
2 234 185
2 44 59
1 114 251
1 63 149
1 83 192
2 264 215
1 179 183
1 139 244
1 95 320
1 114 162
1 40 228
1 96 145
2 11 61
2 148 181
1 133 199
1 40 320
2 154 242
1 76 81
1 63 242
2 167 107
2 201 330
2 45 114
1 31 186
1 90 105
1 186 198
1 194 252
2 123 156
1 245 318
2 134 164
2 145 84
2 27 105
2 262 266
1 29 156
2 330 247
2 159 295
1 13 199
1 142 254
2 90 110
2 153 108
1 67 198
1 201 296
1 199 272
1 207 303
2 120 61
2 273 40
1 40 274
1 115 193
2 143 193
2 210 254
1 224 324
2 222 198
2 42 86
2 25 57
1 28 60
1 29 236
1 161 319
1 138 303
1 2 240
1 110 222
1 52 250
1 192 295
2 304 181
1 45 75
1 2 287
2 142 22
1 19 114
1 13 225
2 38 36
2 315 108
2 70 268
2 74 93
1 197 330
1 153 312
2 279 274
2 75 111
2 223 310
1 107 299
1 257 286
2 84 101
1 49 63
1 6 142
2 164 102
2 220 322
2 242 111
2 109 16
1 4 6
2 78 300
2 16 185
2 212 5
1 60 226
1 180 321
1 68 71
1 201 337
2 132 92
1 7 92
1 56 194
2 128 113
2 329 231
2 213 268
2 111 314
2 177 232
2 288 225
1 183 244
2 223 1
1 196 287
2 286 279
1 33 51
1 32 133
2 120 266
1 177 299
1 58 305
1 119 210
1 103 177
2 9 201
2 206 72
2 46 289
1 19 269
1 227 277
1 73 206
1 171 172
1 179 180
1 152 254
2 41 185
1 139 246
2 50 262
2 218 195
2 31 127
1 16 198
2 38 159
2 329 267
1 162 280
1 5 100
2 202 317
1 89 138
1 148 171
1 256 310
1 68 108
2 336 176
2 216 291
1 94 275
2 263 54
2 7 196
1 39 299
2 329 102
2 115 167
1 4 253
1 167 269
1 46 232
1 24 142
1 57 143
1 282 296
1 65 107
1 233 279
2 37 183
2 166 12
1 89 103
2 94 61
2 38 214
2 302 9
2 223 146
1 4 131
2 200 173
2 119 312
2 3 193
1 57 261
1 329 335
1 140 185
2 83 49
1 188 306
1 166 198
1 28 33
1 136 167
1 209 280
2 84 59
2 276 227
2 114 106
1 188 255
2 218 210
1 77 201
2 274 49
2 104 321
1 51 116
1 8 45
2 194 169
2 255 278
1 21 67
2 36 305
1 270 322
2 285 273
2 216 260
2 6 268
2 337 74
2 33 32
1 211 318
1 142 301
2 147 31
1 27 296
1 240 273
2 137 337
1 108 112
1 8 139
1 246 291
1 37 214
1 183 201
1 168 181
1 45 105
2 328 65
2 174 155
1 119 132
1 35 133
1 18 211
1 69 306
1 1 110
2 106 63
1 237 268
1 66 192
2 304 150
2 3 276
2 31 74
1 55 76
1 81 252
1 252 264
1 43 245
1 159 193
1 29 97
2 105 8
1 97 217
1 124 271
2 314 154
2 213 146
2 34 12
1 21 305
2 215 110
2 173 31
1 97 158
1 75 168
1 55 144
2 145 114
1 50 115
1 188 222
2 27 154
2 30 195
1 258 289
2 108 307
1 122 281
1 35 204
1 189 201
1 26 142
2 325 285
1 200 261
2 13 151
1 126 200
1 103 251
1 190 204
1 258 272
2 210 313
1 115 262
1 184 312
1 268 321
2 98 133
1 30 291
2 320 222
2 17 208
1 175 231
2 44 210
2 43 8
1 292 300
1 20 337
2 292 33
2 98 198
2 275 259
1 96 233
1 18 89
1 2 338
1 64 305
2 210 24
2 45 160
1 45 254
2 253 197
2 109 102
1 161 242
1 18 19
2 57 304
2 153 2
1 86 137
1 106 224
1 28 259
2 44 32
2 216 33
1 136 231
1 55 65
2 46 60
2 72 61
1 104 106
1 115 143
1 128 293
1 139 203
2 93 197
1 83 191
1 82 309
2 299 277
1 290 335
2 163 202
1 123 284
1 7 304
2 33 148
1 319 330
2 45 183
1 110 328
1 118 142
1 123 134
1 240 332
1 156 255
2 166 195
2 39 99
2 34 172
1 161 283
1 29 53
1 80 103
2 232 311
2 36 251
1 81 253
1 46 228
1 260 293
2 145 74
1 58 180
1 167 194
2 56 249
1 226 329
1 39 190
1 213 301
1 274 331
1 244 310
2 58 337
1 194 229
2 280 101
1 99 260
1 159 209
2 211 334
2 239 153
2 292 323
2 241 266
2 16 91
2 219 101
1 102 297
2 186 256
1 60 291
2 118 158
1 60 231
1 165 248
1 220 273
2 261 287
2 11 18
2 181 316
1 8 185
2 267 105
2 325 61
2 326 53
1 179 256
2 338 183
1 128 190
1 259 265
2 214 85
2 123 178
1 74 176
2 314 29
1 124 211
2 147 256
1 136 245
1 169 207
2 262 82
1 67 233
1 29 258
2 229 31
2 11 96
1 7 41
1 4 112
1 247 334
2 186 190
1 46 139
1 9 324
1 153 204
1 8 42
1 177 300
2 167 176
1 154 288
2 147 337
1 105 290
1 102 129
2 49 46
1 101 126
1 138 186
1 79 316
1 33 278
2 45 164
2 34 172
2 127 5
2 91 16
1 169 292
2 137 170
2 239 27
2 50 94
1 137 275
2 180 112
2 60 234
1 220 230
2 321 333
2 181 19
2 123 53
1 103 190
2 284 73
1 112 202
1 80 299
1 27 147
1 199 247
1 120 146
1 54 250
2 9 100
1 36 182
2 32 64
1 82 288
2 212 323
1 110 301
2 200 16
1 114 333
2 303 245
2 220 263
1 191 327
2 128 58
1 210 303
1 49 114
2 293 148
1 119 338
2 135 77
1 15 46
2 191 22
1 17 244
2 110 101
2 262 257
2 219 264
1 102 309
1 29 233
1 162 311
1 71 278
1 183 299
1 72 334
2 97 156
1 137 141
1 74 126
1 33 188
2 148 45
2 321 288
1 44 130
1 91 261
2 202 94
1 226 242
2 208 217
1 263 310
1 10 246
1 133 307
2 336 83
1 3 59
2 163 219
1 117 198
2 219 229
1 233 246
2 198 273
1 200 250
1 231 246
2 254 106
2 173 269
2 200 139
2 40 128
1 273 286
2 248 35
2 232 130
2 226 223
1 187 223
1 63 135
2 93 257
1 15 206
2 79 60
1 201 312
1 6 117
1 136 311
2 14 50
1 169 202
1 51 168
1 193 313
1 176 211
1 18 296
2 184 318
1 312 327
2 295 219
2 319 177
2 267 235
2 67 248
2 107 6
2 185 76
1 82 246
2 227 13
2 222 174
1 144 287
1 39 292
2 179 217
2 303 314
2 247 332
2 17 129
1 10 149
1 40 134
1 7 288
1 227 318
1 18 152
2 193 232
1 163 288
1 249 254
1 8 284
1 28 106
1 29 213
2 85 125
2 149 26
2 263 33
2 183 87
2 271 250
2 113 143
2 332 300
2 327 226
2 17 222
2 330 14
1 65 187
1 119 152
2 51 121
1 58 304
2 306 279
1 96 305
1 56 177
2 120 179
2 110 151
2 122 300
1 34 45
1 181 210
2 173 54
1 250 284
1 169 312
2 40 82
2 11 99
1 87 335
2 154 262
2 220 123
2 97 56
1 24 49
2 20 30
1 8 101
2 284 109
1 292 306
2 193 264
1 130 140
2 259 266
2 182 300
2 52 205
2 243 56
1 134 196
2 276 99
1 4 191
1 133 257
2 97 263
2 173 9
2 155 244
2 239 265
1 146 274
2 163 259
2 26 112
2 174 58
2 269 307
2 252 332
1 138 315
1 3 64
1 110 111
1 239 320
2 307 91
2 103 22
1 68 288
2 72 66
1 48 322
2 296 121
1 207 242
2 211 161
1 94 338
2 42 123
1 12 137
2 158 112
2 5 258
2 29 197
1 119 277
2 226 33
2 267 280
1 87 216
2 302 30
1 215 333
1 141 153
2 220 155
1 205 286
2 232 54
2 135 145
1 49 311
2 69 143
2 85 175
2 7 115
2 260 70
1 15 34
1 80 147
1 56 269
1 286 337
1 208 228
2 9 8
1 103 312
2 220 295
2 209 152
1 23 64
2 296 38
2 331 186
1 183 293
2 237 303
2 212 99
2 301 137
2 276 233
2 183 304
2 211 101
1 53 204
2 227 15
1 13 237
2 319 57
2 29 147
2 276 328
2 143 73
1 90 262
2 82 317
1 141 227
2 329 50
1 122 326
1 79 323
1 301 324
2 28 330
2 167 7
1 76 285
2 140 315
1 43 153
1 123 162
2 215 283
2 15 112
2 304 6
2 125 46
1 183 239
1 210 318
2 38 175
1 231 314
1 192 248
2 306 241
2 338 128
1 20 120
2 174 49
2 64 114
2 266 230
1 175 233
2 31 82
2 126 325
2 100 300
2 127 266
1 112 183
1 147 194
1 248 329
2 179 143
2 58 198
2 54 43
2 7 314
1 43 140
1 182 243
1 109 332
2 267 198
2 19 256
1 155 234
1 210 241
2 28 41
1 214 268
2 179 23
2 231 99
2 116 176
1 201 285
2 234 82
1 157 174
2 53 255
1 125 297
1 243 331
1 57 141
2 252 46
2 225 299
1 120 134
2 321 1
2 300 76
1 262 289
1 13 276
1 86 306
1 71 176
1 76 178
2 288 328
2 10 5
2 186 155
2 252 187
2 330 52
2 174 238
2 296 114
2 289 115
2 144 229
1 153 244
2 108 230
1 133 152
1 128 150
2 224 204
2 5 161
2 200 160
1 95 154
2 233 225
2 108 326
1 14 291
1 16 308
2 298 19
2 238 102
1 54 101
2 265 8
1 136 296
1 13 272
2 147 222
2 22 16
1 184 259
1 213 259
1 76 289
1 30 208
1 159 289
1 55 151
1 174 183
2 215 233
1 135 287
1 56 227
1 79 327
2 123 72
1 180 251
2 294 165
1 13 225
2 11 173
1 106 298
1 40 135
1 99 323
2 145 237
2 56 252
2 291 165
2 315 35
1 98 251
1 30 39
1 162 177
1 148 156
1 75 246
1 149 283
1 163 174
2 24 33
1 105 166
1 78 308
1 72 256
2 52 126
2 221 322
2 272 281
1 104 283
2 291 192
1 83 213
1 163 273
2 6 151
2 229 295
2 293 219
2 263 321
2 289 164
2 311 334
1 172 257
1 125 277
1 132 182
1 33 180
2 59 129
1 64 253
2 262 106
2 5 291
2 250 304
2 101 13
1 150 303
2 332 310
2 159 259
1 114 280
1 25 94
2 308 336
1 7 141
2 77 84
1 28 147
1 169 182
1 208 244
1 222 248
2 164 85
1 59 95
2 101 72
1 123 184
2 136 135
2 296 62
2 257 234
2 87 265
1 92 277
2 274 139
2 309 322
1 45 316
1 77 311
2 203 116
1 256 293
2 326 119
1 175 257
1 169 283
2 286 89
2 336 273
2 232 54
1 83 168
1 74 138
2 143 43
1 99 306
1 242 293
2 322 42
1 81 221
2 314 125
1 18 314
2 157 291
2 273 90
1 215 325
1 36 304
2 123 297
2 286 149
1 57 244
1 114 267
2 322 57
1 57 81
2 225 280
1 148 319
1 44 287
2 171 129
2 71 116
1 56 182
2 274 1
1 161 322
1 28 288
2 161 172
2 86 185
1 139 248
1 228 303
1 214 225
2 209 164
2 6 114
1 158 267
1 50 235
2 159 54
2 58 121
1 192 323
2 273 201
1 69 252
1 45 178
1 60 176
2 76 125
1 45 333
2 30 172
1 10 37
2 91 273
1 145 232
2 114 70
1 48 154
2 113 178
1 36 98
1 152 314
2 80 299
1 88 111
2 253 335
2 198 32
2 168 283
2 255 155
1 26 84
2 88 278
1 100 276
2 116 113
1 6 40
1 299 315
1 37 164
2 209 42
2 35 19
1 93 309
2 311 145
2 71 297
2 62 217
2 310 223
2 34 17
1 2 134
1 220 299
1 179 225
2 30 73
1 201 242
1 269 295
2 238 52
2 240 307
1 209 281
2 177 331
2 320 277
1 7 47
2 54 281
1 3 158
1 167 219
1 208 287
1 20 178
1 93 204
2 31 146
2 122 325
2 269 70
1 38 157
1 220 248
1 60 205
2 88 278
1 2 272
1 142 312
1 144 247
2 173 331
1 54 189
1 249 295
2 7 154
2 79 183
1 1 14
1 56 292
1 3 32
2 36 86
1 46 130
1 9 98
2 289 288
2 253 62
2 309 31
1 211 304
2 67 237
2 42 11
1 171 288
2 12 30
1 82 162
1 183 213
2 219 271
1 107 268
2 80 133
2 230 280
2 87 176
1 154 282
1 245 280
2 242 82
1 178 193
1 141 306
2 131 318
1 67 330
1 174 208
1 122 217
2 269 81
1 34 235
2 187 67
1 205 252
1 166 247
2 65 337
2 86 11
1 32 190
2 122 173
1 116 319
2 180 236
1 27 86
1 28 169
1 121 167
1 41 233
1 266 331
2 67 69
1 31 305
2 274 108
1 35 235
2 73 336
2 298 194
2 76 167
2 42 171
2 66 33
1 276 302
2 184 236
1 90 167
1 125 258
1 219 338
2 34 155
2 22 205
2 137 184
2 10 207
2 206 146
2 233 64
2 177 96
2 226 41
2 79 255
1 26 254
2 306 22
2 144 261
1 26 92
2 80 17
2 255 133
2 96 31
2 264 336
1 229 322
1 83 265
2 53 33
2 53 52
1 150 324
1 58 115
1 14 217
2 303 50
2 250 263
2 288 228
1 131 212
1 41 164
1 324 337
2 108 41
2 30 265
1 141 304
1 91 312
2 97 209
1 53 141
1 44 328
2 215 296
1 182 233
1 248 331
1 65 127
2 26 215
2 109 149
1 85 127
1 1 248
1 145 318
1 75 234
2 223 199
2 7 40
2 148 105
2 58 196
2 304 79
1 6 26
2 14 287
1 3 168
2 337 205
1 250 302
2 101 111
2 224 274
1 61 87
1 174 327
2 128 64
2 98 78
1 214 271
2 147 316
1 104 171
2 311 246
2 32 250
2 8 261
2 85 93
2 261 2
2 125 118
2 129 307
2 110 205
1 251 334
1 227 314
1 27 206
1 31 54
2 298 249
1 148 245
1 163 228
2 177 77
1 85 134
1 15 91
2 234 153
2 317 8
2 108 96
2 116 259
1 45 175
2 143 118
1 29 163
1 119 208
2 237 93
1 56 173
1 74 172
1 62 214
1 13 285
2 209 200
2 211 194
2 119 23
2 322 270
2 172 115
1 117 247
2 83 94
1 66 192
1 94 163
2 19 297
1 15 233
1 116 130
2 51 110
1 22 204
2 99 145
2 319 40
2 298 54
1 290 319
2 114 190
1 51 248
1 4 112
1 9 302
2 214 10
2 332 194
1 165 307
1 8 216
2 269 59
1 119 189
1 65 151
2 165 83
2 28 53
2 33 229
2 83 61
1 102 240
1 312 328
2 110 229
2 94 85
2 33 320
2 162 86
2 235 279
1 213 332
1 39 137
1 238 295
2 288 28
1 75 251
1 168 249
2 98 304
1 30 202
1 22 233
2 28 151
2 164 228
2 41 280
2 218 309
1 30 112
1 152 159
2 251 26
2 331 45
2 34 281
2 257 42
1 95 182
1 110 129
2 119 237
1 141 306
2 221 28
1 21 59
2 5 67
1 58 269
2 73 234
1 8 209
2 246 54
1 67 269
2 145 252
2 18 212
1 39 267
1 58 322
1 148 282
2 258 251
2 285 338
1 129 299
1 87 289
1 242 291
1 248 263
2 306 77
2 22 219
2 239 251
2 94 289
1 115 177
2 125 327
2 285 338
1 45 331
2 128 290
2 208 64
2 266 256
2 297 81
2 283 40
1 156 244
2 94 69
2 30 70
1 71 292
2 248 86
2 242 55
1 2 218
2 286 46
1 267 269
2 263 127
2 25 221
1 158 182
2 318 161
1 169 256
1 151 272
1 82 291
2 61 226
1 100 174
1 143 215
1 97 255
1 141 200
2 115 76
1 76 240
2 74 131
2 336 267
2 147 28
1 204 315
2 69 98
1 60 121
2 155 263
1 3 304
2 72 96
1 209 234
1 20 100
1 237 282
2 182 154
2 20 114
2 293 271
1 78 325
1 328 338
1 148 174
2 284 78
2 13 61
1 23 289
2 267 98
1 151 247
2 32 84
1 90 286
1 12 211
1 164 209
1 75 307
2 242 102
1 220 240
1 91 263
2 147 165
1 241 338
1 52 214
1 137 183
2 223 121
2 86 123
2 255 267
1 199 215
1 11 46
1 135 142
2 259 14
2 220 104
1 82 133
2 251 333
1 71 108
1 17 82
2 334 280
1 235 257
1 64 89
2 126 225
2 218 336
2 15 102
1 181 264
2 300 83
1 67 250
2 184 239
1 264 283
1 106 227
2 192 119
1 51 282
1 31 166
2 316 82
2 271 148
2 233 29
1 52 184
1 25 232
2 25 264
2 59 127
2 43 268
2 22 291
2 70 147
2 73 256
2 59 72
2 273 245
2 2 264
2 75 313
1 31 304
1 134 139
1 87 164
2 199 113
2 61 81
2 229 86
1 99 220
2 249 206
2 324 213
2 84 45
1 84 326
2 300 281
2 310 172
1 61 290
2 202 27
2 94 286
2 123 56
2 224 290
1 25 169
1 21 150
1 137 328
1 143 284
1 123 237
2 186 136
1 28 56
2 152 23
1 224 233
1 115 132
1 126 227
1 211 292
2 92 302
2 289 213
1 26 315
1 78 245
1 43 301
2 155 33
1 27 295
1 156 282
1 60 109
2 256 98
2 129 67
2 119 291
1 72 327
1 37 215
2 223 82
1 227 263
1 103 136
2 230 66
2 181 233
2 58 50
1 10 113
1 307 315
2 132 197
2 313 175
1 9 267
1 24 251
1 209 276
1 50 254
2 76 15
1 53 146
1 49 212
2 329 311
1 246 286
2 27 115
2 40 96
1 24 286
1 265 296
2 237 90
2 175 281
2 196 97
1 48 230
2 67 65
1 56 250
2 159 301
2 216 104
2 195 249
2 188 2
2 278 209
1 138 331
2 104 171
2 68 151
1 37 317
1 91 100
2 312 95
2 157 329
2 64 231
1 33 101
1 177 294
2 234 143
2 47 169
2 316 23
2 102 237
2 133 261
1 81 153
1 220 240
2 330 149
2 64 140
2 44 188
2 140 9
1 93 176
1 97 253
2 65 275
1 205 297
2 6 261
2 183 206
2 267 335
1 141 336
1 134 226
2 292 297
1 192 310
2 102 135
2 269 289
1 115 321
2 102 139
1 5 213
1 67 145
1 45 223
1 20 142
2 161 169
1 189 195
2 29 77
2 3 129
1 287 306
1 254 328
1 158 265
2 222 284
2 155 101
2 185 226
2 9 204
2 99 17
2 162 329
2 124 111
1 298 332
1 22 324
1 41 283
2 95 58
1 38 161
1 101 168
1 235 334
2 93 144
1 107 182
1 293 316
1 49 301
1 130 225
1 178 286
1 132 250
1 129 253
1 48 146
1 2 309
2 279 289
2 183 32
2 328 167
2 89 143
1 149 270
2 320 205
1 159 285
1 119 321
1 230 235
1 65 128
1 173 335
1 31 138
2 102 62
1 70 267
2 247 213
2 21 133
2 113 300
1 290 308
2 257 251
2 268 59
1 121 247
1 248 271
2 250 331
2 136 65
2 9 13
1 257 320
2 277 92
2 256 175
1 18 45
1 29 262
1 202 284
1 56 281
2 105 236
1 42 128
2 61 150
1 113 237
1 188 301
2 70 161
1 170 305
2 291 194
2 211 182
1 134 144
1 243 309
1 122 126
2 204 100
1 3 99
2 105 329
2 71 63
1 182 301
1 139 171
2 292 42
1 3 326
1 11 82
2 90 166
1 102 309
1 151 239
1 71 208
1 68 303
1 40 176
1 83 275
1 30 142
2 150 185
2 277 69
2 303 151
1 117 155
2 253 196
2 214 338
1 6 289
2 191 125
1 1 69
1 128 143
2 111 225
2 198 16
1 155 263
2 224 60
1 193 232
1 195 221
1 21 63
2 325 54
2 338 112
2 129 302
1 125 307
1 46 309
2 118 195
2 99 131
2 129 44
2 187 34
2 42 257
1 111 198
2 28 123
2 73 15
1 73 192
1 61 70
2 20 43
2 16 134
2 136 57
2 66 330
2 242 180
2 292 210
2 254 155
2 6 286
2 156 175
2 36 246
1 219 249
2 84 222
2 5 283
2 213 92
1 132 203
2 286 88
2 282 224
2 162 70
2 140 306
1 10 275
1 224 294
1 45 299
2 145 175
2 125 200
1 127 258
1 11 179
2 146 191
2 86 108
1 36 268
2 99 50
1 281 290
2 149 133
2 75 147
2 1 70
2 298 54
2 188 331
1 147 284
2 336 316
1 83 201
2 293 301
2 148 38
1 156 314
2 211 214
2 205 84
1 12 333
2 222 196
1 30 66
2 175 17
2 287 215
1 82 199
2 32 108
2 55 98
1 95 217
1 122 227
1 108 210
1 278 281
1 64 199
2 127 211
2 306 297
2 70 199
1 246 271
2 135 110
1 117 293
2 73 48
2 57 12
1 93 334
2 39 146
1 92 311
1 33 235
1 253 274
1 97 160
1 6 63
1 29 218
1 138 289
2 242 299
2 268 172
2 56 187
1 186 249
2 4 331
2 248 246
1 42 112
2 338 13
2 13 216
1 61 333
2 148 269
2 12 183
1 55 199
2 282 132
1 85 97
2 93 9
2 176 4
1 133 301
1 207 295
2 73 70
1 38 169
1 40 156
2 202 138
1 251 319
2 314 273
1 38 96
1 184 214
2 38 44
2 82 300
1 51 111
1 25 312
1 24 28
1 50 326
1 324 338
2 50 256
1 123 219
1 80 252
1 34 328
2 169 257
1 3 213
2 283 316
1 102 320
2 241 82
2 75 282
1 210 218
2 37 256
2 49 285
2 20 183
2 288 305
2 268 50
1 103 225
2 41 124
2 67 26
2 19 94
2 235 118
2 226 331
2 180 176
1 54 73
2 331 197
1 282 335
2 29 9
1 135 288
1 166 273
2 99 248
2 32 261
2 281 127
1 107 327
1 247 324
2 109 85
2 210 130
2 192 87
2 329 266
2 88 96
2 227 205
2 13 266
1 168 286
2 149 7
1 86 215
2 190 34
1 311 335
1 28 199
2 94 143
1 119 254
1 80 259
2 289 20
2 15 241
2 267 72
2 105 290
2 215 8
2 183 281
2 191 8
2 168 150
2 255 54
2 116 141
2 219 105
1 222 286
2 257 190
1 10 93
2 148 271
1 257 319
1 45 67
1 128 286
1 59 207
2 105 336
1 19 292
2 265 131
1 178 331
1 11 192
2 5 222
1 112 155
1 91 223
1 72 201
2 278 39
2 191 115
2 126 101
1 46 337
2 55 62
1 45 255
2 308 134
2 1 242
2 125 229
2 140 89
1 174 288
2 249 25
2 101 15
2 261 279
2 29 242
2 179 147
1 19 245
2 43 311
1 239 312
1 78 232
2 277 86
2 208 136
1 5 50
2 103 318
2 31 160
2 304 227
1 124 331
1 81 146
2 14 69
1 247 263
2 122 105
2 129 137
1 171 315
2 287 226
1 40 172
1 256 284
1 208 258
2 157 39
1 109 186
1 45 262
1 6 202
1 46 75
2 316 182
2 284 47
1 300 327
1 175 293
1 15 16
1 25 186
1 52 210
1 119 284
2 291 148
1 9 132
1 162 321
2 71 98
1 3 120
2 321 305
1 171 174
1 268 313
2 311 336
2 90 258
1 102 225
2 278 208
2 17 82
2 277 297
2 162 59
2 227 22
2 333 257
2 93 239
1 305 329
1 13 330
1 90 140
1 150 274
1 17 79
2 134 290
2 10 290
1 119 164
2 64 91
1 166 331
1 42 311
1 220 333
1 63 132
2 71 53
2 301 104
1 34 210
2 335 194
1 6 290
2 99 48
2 278 317
2 148 4
1 2 259
2 33 70
1 62 171
1 99 114
2 39 128
1 52 139
2 123 216
2 159 21
1 72 148
1 21 189
2 59 73
2 160 143
2 326 212
1 132 171
1 180 306
2 303 62
2 158 274
1 184 252
2 182 276
1 247 283
1 53 132
1 114 200
2 91 41
1 263 328
1 57 182
2 149 291
1 331 338
2 55 177
2 309 24
2 128 323
1 7 53
2 18 133
1 84 140
2 321 16
2 15 215
2 12 97
1 164 250
2 170 102
1 42 326
2 70 95
1 139 168
1 123 292
1 86 94
2 37 97
2 290 185
1 25 313
2 45 113
1 68 302
1 164 188
2 8 147
2 220 234
2 198 261
2 334 266
2 177 162
1 122 325
1 24 205
2 289 265
1 181 300
2 76 322
1 171 269
2 158 156
1 208 230
2 112 104
1 139 150
1 42 156
1 43 154
1 13 53
2 156 297
2 36 287
1 195 273
1 14 29
2 55 22
1 155 161
2 264 200
2 111 93
2 59 9
2 238 78
1 59 251
2 177 125
1 52 99
1 218 220
1 192 258
2 284 133
2 180 270
2 145 107
1 81 189
1 239 256
1 70 77
2 91 37
1 84 303
2 5 330
1 206 209
1 77 310
2 5 47
1 91 282
2 17 312
2 170 117
1 124 242
2 185 191
2 332 35
2 333 193
2 99 17
2 71 51
1 270 330
1 113 314
2 28 215
1 77 326
2 126 169
1 163 224
1 19 195
2 188 14
1 65 102
2 226 193
2 257 1
2 245 6
2 255 208
2 35 228
2 221 300
1 59 292
2 178 172
2 113 84
1 90 140
1 177 202
1 18 292
2 313 169
2 181 119
2 268 43
1 144 301
1 119 138
2 39 218
1 38 190
1 177 236
2 12 45
1 299 321
1 18 284
1 98 225
1 239 304
1 152 318
2 115 85
2 68 266
1 173 181
1 16 30
1 210 251
1 152 198
2 74 330
1 297 314
2 67 66
1 197 290
1 62 266
2 42 242
1 45 124
2 311 6
2 236 38
2 186 134
2 126 115
1 252 305
1 136 187
2 310 185
1 92 143
1 115 250
2 173 333
1 197 291
1 238 338
1 122 165
2 248 133
1 218 271
2 134 7
1 139 323
2 57 253
1 158 240
1 69 309
2 318 277
1 224 245
1 234 304
2 74 76
2 78 30
2 283 38
1 71 224
2 201 27
1 9 265
1 150 228
2 82 55
2 120 282
1 20 256
2 120 139
2 284 118
2 15 4
1 171 210
1 163 197
2 219 261
1 2 152
1 25 124
2 228 99
1 178 278
1 168 329
1 100 268
1 102 147
2 240 43
1 164 259
1 227 286
2 113 329
1 63 253
2 34 43
2 92 170
2 301 134
2 49 209
1 111 162
1 45 220
2 65 24
2 332 193
2 102 337
2 304 23
2 225 128
1 235 297
2 181 221
1 127 254
1 78 223
1 15 227
1 20 210
1 156 239
1 53 189
2 119 314
1 32 125
2 173 223
1 83 130
2 113 2
1 160 198
2 220 173
1 185 196
1 112 245
2 179 79
1 52 155
2 96 334
2 4 88
2 290 4
2 62 185
2 178 27
2 215 46
2 16 328
1 83 155
2 207 2
1 140 334
2 130 280
2 63 83
1 20 183
1 51 108
2 282 165
2 246 166
1 138 299
2 2 311
2 152 4
1 124 232
2 272 58
2 294 302
2 216 271
2 91 289
2 9 117
2 75 47
1 36 170
2 286 3
2 131 247
2 17 38
2 79 145
2 250 32
1 26 203
2 78 74
1 134 226
1 209 233
2 71 225
2 5 206
1 190 193
1 130 189
1 142 162
1 228 327
2 63 233
2 138 247
1 205 303
2 80 15
2 306 168
1 269 302
1 95 141
2 105 19
2 231 221
1 32 315
2 81 74
1 200 290
2 23 203
1 34 150
1 33 189
1 117 312
1 7 164
1 199 279
2 238 256
1 68 152
2 114 175
2 324 93
1 27 217
1 190 195
2 172 210
1 216 277
2 293 88
1 80 215
2 33 151
2 284 53
2 180 181
2 276 35
2 196 331
1 152 241
2 218 31
1 138 203
2 213 193
1 10 274
1 184 188
1 28 165
1 31 40
1 39 46
1 176 247
2 292 275
1 235 332
样例输出
53
125
99
148
384
235
240
123
81
275
113
180
350
162
106
251
149
188
72
163
239
160
231
223
124
24
337
203
91
130
41
235
137
41
115
91
68
190
81
135
78
18
71
170
150
106
309
153
205
129
21
129
212
93
82
116
178
24
15
113
306
262
216
3
147
158
175
119
19
87
90
194
155
115
164
226
111
237
118
315
174
151
34
154
43
140
97
38
350
24
295
11
307
182
107
213
303
27
132
173
60
34
219
372
20
17
41
143
119
69
261
72
264
175
91
232
120
103
176
188
70
199
62
291
283
301
133
88
278
90
148
318
148
165
216
23
5
12
385
20
281
4
31
26
137
209
274
109
118
50
179
95
51
86
24
8
230
327
157
246
270
113
174
238
107
9
91
176
111
154
55
22
221
97
13
189
142
180
51
8
229
29
60
205
83
95
111
275
91
121
306
105
37
1
112
187
136
57
120
107
160
4
146
173
263
126
3
266
254
14
87
43
259
165
135
286
120
69
83
8
50
169
157
17
120
97
225
171
13
81
169
352
121
100
125
33
323
138
21
141
34
22
90
40
51
250
103
102
216
63
79
292
94
145
127
179
33
52
66
274
119
16
39
75
148
163
106
32
143
180
137
146
14
160
23
213
184
49
177
111
15
339
141
296
42
358
275
48
132
275
273
72
266
125
179
161
45
233
332
50
218
3
25
221
183
30
58
11
112
163
213
149
78
8
162
34
273
67
242
165
153
305
189
140
77
86
251
53
114
330
99
164
56
17
4
19
78
176
311
4
295
103
199
90
30
274
4
171
208
12
125
73
214
156
108
63
146
204
195
18
186
36
189
301
315
56
110
101
18
73
193
108
42
122
26
313
56
120
71
171
169
76
184
65
80
41
300
318
279
101
271
45
185
38
204
258
133
73
281
15
47
121
124
110
181
125
81
139
176
355
49
47
85
160
116
169
148
177
390
28
11
96
109
58
106
307
82
102
195
62
130
45
252
148
11
181
266
17
16
129
151
326
37
186
199
222
359
140
225
24
64
313
205
51
175
36
129
136
152
136
124
90
256
77
328
80
155
98
284
195
108
138
122
68
32
262
75
200
121
62
9
179
211
1
50
74
255
159
44
132
115
180
37
44
254
19
39
169
328
8
152
153
156
181
259
210
92
107
58
135
87
123
51
98
65
88
63
119
107
143
149
113
72
266
52
108
216
77
65
46
183
62
183
8
108
246
23
29
99
21
15
208
126
168
224
30
240
86
177
161
13
217
58
33
61
155
205
367
130
143
212
241
29
296
192
159
56
164
208
41
169
118
187
36
182
142
22
134
5
16
33
211
225
151
304
24
198
309
123
84
170
59
357
80
18
3
215
110
31
199
32
197
215
166
351
7
166
235
324
42
66
193
83
232
349