QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69867#5113. Bridgemagicduck#AC ✓1908ms8268kbC++142.0kb2023-01-02 17:25:232023-01-02 17:25:25

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-02 17:25:25]
  • 评测
  • 测评结果：AC
  • 用时：1908ms
  • 内存：8268kb
查看
  • [2023-01-02 17:25:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T> inline void read(T &F) {
    int R = 1; F = 0; char CH = getchar();
    for(; !isdigit(CH); CH = getchar()) if(CH == '-') R = -1;
    for(; isdigit(CH); CH = getchar()) F = F * 10 + CH - 48;
    F *= R;
}
inline void file(string str) {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 1e5 + 10, B = 400;
int n, m, q, op[N], g[N], id[N], tot, flag[N], M; pair<int, int> c[N];
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
__gnu_pbds :: gp_hash_table<int, int> p[B];
void rebuild(int x) {
    const int l = (x - 1) * B + 1, r = x * B;
    __gnu_pbds :: gp_hash_table<int, int> tmp;
    for(int i = l; i <= r; i++)
        if(flag[i]) {
            const int a = g[c[i].second], b = a + 1;
            auto ia = tmp.find(a), ib = tmp.find(b);
            if(ia == tmp.end()) tmp[a] = a; 
            if(ib == tmp.end()) tmp[b] = b;
            swap(tmp[a], tmp[b]);
        }
    p[x].clear();
    for(auto i : tmp) p[x][i.second] = i.first;
}
void ins(int x) {
    flag[x] = 1;
    const int y = (x - 1) / B + 1;
    rebuild(y);
}
int qry(int x) {
    for(int i = 1; i <= M; i++)
        if(p[i].find(x) != p[i].end()) x = p[i][x];
    return x;
}
int main() {
    //file("");
    read(n), read(m), read(q); 
    for(int i = 1; i <= q; i++) {
        read(op[i]);
        if(op[i] == 1) {
            int a, b; read(a), read(b);
            c[++tot] = make_pair(b, i);
            g[i] = a;
        }
        else read(g[i]);
    }
    sort(c + 1, c + tot + 1);
    for(int i = 1; i <= tot; i++) id[c[i].second] = i;
    M = (tot - 1) / B + 1;
    for(int i = 1; i <= q; i++) {
        if(op[i] == 1) ins(id[i]);
        else cout << qry(g[i]) << '\n';
    }
    #ifdef _MagicDuck
        fprintf(stderr, "# Time: %.3lf s", (double)clock() / CLOCKS_PER_SEC);
    #endif
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3548kb

input:

3 4 13
2 2
1 1 3
2 1
2 2
2 3
1 2 4
2 1
2 2
2 3
1 2 1
2 1
2 2
2 3

output:

2
2
1
3
3
1
2
3
2
1

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 158ms
memory: 5164kb

input:

3 100000 99997
2 2
2 2
2 3
2 3
2 3
2 3
2 3
1 2 11047
1 1 98732
1 2 90045
1 1 43556
2 1
2 3
1 2 17242
1 1 17027
2 1
1 1 94195
2 1
2 2
2 1
2 3
1 1 34124
1 2 14354
1 2 673
1 2 39812
1 2 35520
1 2 16046
2 3
2 2
1 1 25410
2 3
2 1
2 3
2 2
1 2 55684
2 1
1 2 24811
1 2 92268
1 2 60268
2 2
1 1 89272
1 2 19232...

output:

2
2
3
3
3
3
3
3
2
1
2
1
2
3
3
1
1
2
1
3
3
2
1
3
2
1
2
1
2
2
2
2
1
1
2
1
3
2
1
3
2
1
3
2
2
1
3
3
2
3
2
3
1
2
1
1
2
3
2
1
3
2
3
2
3
2
2
1
1
2
1
1
2
3
2
1
1
3
1
1
2
2
3
2
2
1
1
1
2
3
3
1
1
2
1
1
3
1
3
2
3
2
3
2
2
2
3
3
2
2
2
3
3
2
2
2
3
1
2
1
1
3
2
3
2
2
2
1
1
1
3
3
3
2
1
1
3
3
3
1
1
2
3
2
3
3
3
3
2
3
...

result:

ok 60761 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 3348kb

input:

100000 5 20
1 40277 1
2 55431
2 22404
2 29137
2 10206
2 72758
2 92880
1 96104 2
2 12641
1 99618 2
2 88481
1 76531 3
1 91957 5
1 23999 2
2 35922
1 69730 5
1 16353 2
1 90312 1
1 75264 5
2 77283

output:

55431
22404
29137
10206
72758
92880
12641
88481
35922
77283

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 3400kb

input:

3 5 20
2 3
1 2 2
2 3
1 1 4
2 1
1 2 5
1 1 1
2 1
2 2
2 1
2 1
2 2
2 3
2 3
2 1
2 1
2 1
2 3
2 2
2 3

output:

3
2
2
2
3
2
2
3
1
1
2
2
2
1
3
1

result:

ok 16 numbers

Test #5:

score: 0
Accepted
time: 714ms
memory: 5872kb

input:

200 100000 99995
1 180 45150
2 137
1 97 78979
1 14 74747
1 151 41036
1 178 88736
1 26 50618
1 132 72623
1 95 37475
2 184
1 31 44675
1 183 14874
1 66 14597
2 191
2 102
1 27 61558
1 36 39304
2 119
2 185
1 156 50000
2 200
2 152
1 17 51778
1 39 39403
2 168
1 50 67213
1 92 56771
2 28
2 196
1 99 29006
2 4...

output:

137
184
191
102
119
185
200
151
168
27
196
43
73
16
28
64
88
106
139
117
90
131
64
64
107
11
38
149
133
184
166
20
95
185
71
85
151
96
106
103
91
45
195
112
82
113
183
178
47
112
12
185
41
153
77
179
44
165
84
111
192
161
144
33
139
9
37
38
177
45
146
83
88
166
1
180
175
180
12
166
186
44
2
115
124
...

result:

ok 50281 numbers

Test #6:

score: 0
Accepted
time: 116ms
memory: 4836kb

input:

200 100 100000
1 192 88
1 13 2
2 131
1 80 44
1 11 74
1 159 89
1 29 91
1 81 62
1 159 21
1 37 34
2 169
2 163
1 164 50
1 104 45
1 81 46
1 176 73
1 68 59
2 117
2 152
2 189
1 125 4
2 45
1 120 59
2 30
2 113
1 74 15
1 147 71
1 31 47
2 179
2 118
2 34
2 61
1 41 32
2 153
1 186 28
2 113
2 55
2 24
2 92
2 72
2 8...

output:

131
169
163
117
152
189
45
29
113
179
118
34
61
153
113
55
24
92
72
8
152
85
174
188
18
158
152
164
101
156
79
81
146
15
94
90
23
81
200
153
181
181
135
31
145
44
88
143
11
134
25
80
183
79
187
29
92
195
123
76
14
135
28
193
116
33
179
76
45
169
91
85
141
138
166
195
53
117
127
86
84
101
132
115
1
9...

result:

ok 91618 numbers

Test #7:

score: 0
Accepted
time: 2ms
memory: 3356kb

input:

10 100 20
1 7 12
1 7 48
2 7
1 4 92
2 4
2 7
2 6
1 8 23
2 1
1 8 83
2 3
1 8 33
1 9 72
2 1
2 8
1 9 4
1 6 6
2 1
2 1
2 10

output:

7
5
7
6
1
3
1
9
1
1
10

result:

ok 11 numbers

Test #8:

score: 0
Accepted
time: 713ms
memory: 5724kb

input:

200 100000 99995
1 1 29447
2 147
2 132
2 90
1 140 58754
2 74
2 51
2 113
1 177 51453
1 160 35609
2 47
1 88 93756
2 17
2 180
1 9 95689
2 196
1 59 45390
2 90
1 156 83976
2 17
1 66 13781
1 68 82550
2 174
2 14
1 24 41452
1 29 39524
2 2
1 190 55163
1 27 80396
1 102 20535
2 112
2 66
1 69 84633
1 95 51235
1...

output:

147
132
90
74
51
113
47
17
180
196
90
17
174
14
1
112
67
73
58
93
61
41
54
90
9
14
28
61
42
118
15
137
119
127
162
118
100
83
177
171
159
30
24
23
183
120
90
104
102
70
70
62
88
111
149
37
168
75
54
175
132
164
89
114
69
132
184
81
62
38
197
101
24
115
187
16
153
170
29
142
191
134
165
41
168
171
11...

result:

ok 50221 numbers

Test #9:

score: 0
Accepted
time: 7ms
memory: 4128kb

input:

3 100 99997
1 1 47
2 2
2 1
1 1 46
1 1 9
2 1
1 1 98
2 1
1 2 93
1 2 71
1 2 67
2 2
1 1 43
2 1
2 2
2 2
1 1 85
1 2 86
1 2 97
1 1 84
2 3
2 1
2 3
1 1 23
2 3
1 1 13
1 2 34
2 3
2 3
2 3
1 2 94
2 1
1 2 31
2 3
2 1
2 2
2 3
2 3
2 3
1 1 83
2 1
2 3
1 2 77
2 3
2 1
2 3
1 2 89
2 3
2 3
1 1 74
2 3
2 2
2 2
2 1
1 1 78
2 1...

output:

1
2
2
1
2
2
3
3
1
2
1
1
2
2
2
3
3
2
1
3
3
3
1
3
2
1
2
2
2
2
3
3
1
1
1
1
1
2
3
3
2
3
1
3
1
1
2
2
3
2
3
3
1
2
2
1
3
3
2
3
2
1
3
3
1
3
3
3
3
1
2
3
2
3
1
3
1
1
3
3
1
2
1
1
3
3
2
1
2
3
2
1
1
1
2
1
3
2
3
1
2
2
3
2
3
1
2
1
1
3
2
1
1
3
3
1
2
3
2
1
3
3
2
1
3
3
1
2
3
3
2
1
3
1
2
2
3
2
1
2
2
3
3
3
2
2
3
3
2
2
...

result:

ok 99897 numbers

Test #10:

score: 0
Accepted
time: 8ms
memory: 4160kb

input:

10 100 99996
2 2
2 1
2 5
1 8 23
1 5 44
1 6 86
1 3 38
1 5 65
1 8 87
1 6 9
1 6 62
2 4
2 10
2 6
2 2
1 4 14
1 4 54
1 2 7
2 9
1 1 41
2 8
1 1 52
2 8
1 6 63
2 3
1 2 27
2 1
1 6 99
2 5
1 8 16
1 1 16
1 4 35
2 1
2 4
1 4 25
2 2
1 2 66
2 10
1 7 56
2 5
1 2 70
1 8 32
2 2
1 6 71
2 9
1 6 33
1 8 74
1 6 31
1 7 24
2 10...

output:

2
1
5
3
10
5
2
9
8
8
2
1
3
6
3
2
10
2
2
6
10
4
4
7
1
1
9
7
2
6
5
7
8
5
8
1
10
10
2
7
8
6
7
6
3
9
4
8
4
4
7
4
9
9
1
7
8
6
4
7
7
4
6
10
6
6
3
4
4
10
4
7
8
3
5
3
2
7
9
10
6
6
1
5
6
7
10
10
5
10
2
3
5
6
4
7
9
9
9
9
7
10
3
8
2
4
9
4
9
2
9
5
1
10
8
6
6
1
9
3
6
3
8
9
10
5
10
1
8
9
6
7
3
7
2
8
3
8
10
6
10
2...

result:

ok 99577 numbers

Test #11:

score: 0
Accepted
time: 11ms
memory: 4216kb

input:

10 100 100000
2 6
2 4
2 8
1 5 70
2 4
1 3 55
1 7 89
1 1 57
1 9 40
1 3 83
2 7
2 9
1 5 26
2 7
1 1 99
2 8
1 1 13
2 8
1 3 86
1 6 12
1 5 11
1 9 98
2 2
1 1 63
1 5 67
1 5 66
1 8 58
2 4
1 9 71
1 1 71
1 5 89
1 1 17
2 3
2 10
1 2 59
2 5
2 2
2 5
1 6 8
1 1 45
1 3 69
1 5 63
2 5
1 5 35
1 2 19
1 4 8
2 1
2 1
2 10
1 2...

output:

6
4
8
4
8
10
8
7
7
1
3
4
7
8
2
8
8
2
2
7
4
2
8
4
3
9
10
8
10
10
7
2
6
9
6
5
6
4
8
2
2
8
7
7
4
6
7
4
8
10
10
8
5
5
10
5
10
4
3
3
1
8
7
9
6
2
8
8
2
9
10
7
2
7
5
8
7
8
6
1
5
7
9
5
7
1
6
5
4
2
7
10
1
8
5
4
4
1
1
1
8
3
4
7
3
10
10
10
3
8
6
7
10
4
4
9
2
6
7
2
1
8
4
9
3
7
10
2
8
2
9
10
3
10
10
9
1
4
4
6
5
...

result:

ok 99580 numbers

Test #12:

score: 0
Accepted
time: 1ms
memory: 3328kb

input:

10 100 20
2 9
2 7
2 4
1 2 8
2 8
1 2 1
2 9
1 3 35
1 6 37
1 9 45
1 8 20
2 10
1 6 5
2 5
1 4 91
2 1
1 6 94
1 7 60
1 8 96
1 5 1

output:

9
7
4
8
9
9
5
1

result:

ok 8 numbers

Test #13:

score: 0
Accepted
time: 2ms
memory: 3408kb

input:

200 100000 20
2 67
2 2
2 183
1 113 37023
2 191
1 138 85049
2 118
1 139 45917
2 77
2 22
1 163 58926
2 105
2 47
1 154 52742
2 193
1 7 38889
2 196
2 101
2 55
1 37 36657

output:

67
2
183
191
118
77
22
105
47
193
196
101
55

result:

ok 13 numbers

Test #14:

score: 0
Accepted
time: 171ms
memory: 5092kb

input:

3 100000 100000
1 2 27703
2 1
1 1 4733
2 3
1 1 35779
2 3
1 2 75051
1 1 55567
1 2 67461
2 2
2 3
2 2
1 2 40504
2 2
1 2 66898
2 2
2 2
2 3
2 2
1 1 49407
1 1 40531
2 2
1 1 16364
1 1 20583
2 1
1 2 15074
2 3
1 2 52463
1 2 68707
2 3
1 1 2943
1 1 49490
1 1 21186
2 2
1 2 60207
2 3
1 1 69753
2 2
1 2 55020
1 2 ...

output:

1
2
1
1
2
1
3
2
2
3
2
2
1
1
3
3
1
2
1
3
3
2
3
1
1
3
1
3
2
3
1
2
1
2
3
1
1
1
1
1
3
3
3
3
1
2
1
3
3
3
1
1
2
1
3
3
2
2
1
3
3
3
1
2
2
1
1
2
1
1
3
1
2
1
1
1
3
3
3
2
1
2
1
3
1
1
1
3
2
2
3
1
1
3
2
1
2
2
3
2
3
2
2
3
1
1
3
1
1
2
2
2
2
3
1
1
1
3
1
2
3
3
2
2
2
3
2
2
1
1
1
3
3
2
1
3
1
1
2
1
2
3
2
3
3
1
1
2
3
2
...

result:

ok 60629 numbers

Test #15:

score: 0
Accepted
time: 719ms
memory: 5724kb

input:

200 100000 99996
1 9 50789
2 13
2 119
2 140
2 17
2 152
2 55
1 13 78327
1 86 75223
1 124 45493
1 61 18265
2 27
1 83 46963
2 44
2 2
1 24 66690
1 60 83558
2 190
1 17 74439
1 46 33383
1 33 865
1 65 31179
1 126 66418
1 24 87240
1 157 70780
1 39 64647
2 74
2 112
1 34 94471
1 118 59390
2 122
2 133
2 159
1 ...

output:

13
119
140
17
152
55
27
44
2
190
74
112
122
133
159
1
21
131
102
78
42
117
153
44
56
115
111
15
22
11
30
81
162
11
26
77
190
76
103
137
2
192
107
13
176
88
75
193
59
14
41
196
23
6
114
121
150
143
172
121
119
117
130
179
131
130
138
107
181
45
22
75
6
79
175
177
44
92
167
82
155
197
119
109
167
146
...

result:

ok 50119 numbers

Test #16:

score: 0
Accepted
time: 1908ms
memory: 8264kb

input:

100000 100 99997
2 83146
1 92304 70
2 1316
2 67332
1 3999 7
1 87638 98
2 46517
2 9036
2 72931
1 99147 75
1 81076 94
2 35556
1 38226 77
1 70606 61
1 97514 72
2 59772
1 51823 100
1 34436 19
1 2566 38
2 35420
1 52972 14
1 59064 59
1 61862 80
1 23386 91
1 20343 59
2 40701
2 64037
2 92058
2 58963
2 30254...

output:

83146
1316
67332
46517
9036
72931
35556
59772
35420
40701
64037
92058
58963
30254
960
27193
30536
34081
49930
17706
61236
23210
1769
49001
45989
2314
66544
29516
16869
48166
18813
46466
12667
2769
13587
595
30471
96700
74682
54428
24624
79741
35016
63668
97575
8010
10202
30058
62498
98512
52240
2020...

result:

ok 50227 numbers

Test #17:

score: 0
Accepted
time: 7ms
memory: 4156kb

input:

10 5 100000
1 9 3
1 1 2
1 9 2
2 7
1 8 4
2 3
2 6
1 4 2
2 4
2 5
2 10
2 2
2 8
2 10
2 10
2 8
2 8
2 6
1 5 3
2 3
2 5
1 6 2
2 3
2 5
2 4
1 5 1
1 3 4
2 10
2 3
2 2
1 1 3
1 7 3
1 1 1
2 5
1 4 5
2 4
2 2
1 2 5
2 9
2 5
2 5
2 9
2 3
2 9
2 4
2 8
2 9
2 7
2 8
2 2
2 4
2 8
2 3
2 5
2 8
2 2
2 6
2 2
1 6 4
2 7
2 10
2 7
1 8 1...

output:

7
3
6
5
4
10
1
9
10
10
9
9
6
3
4
3
4
6
10
4
1
9
6
1
8
9
9
8
5
8
6
7
8
4
7
1
6
7
5
9
7
1
2
1
4
10
4
1
1
9
5
10
10
1
6
3
3
1
5
8
6
3
5
5
9
3
1
4
7
1
3
2
6
10
7
10
5
6
2
6
10
8
9
3
8
1
9
2
7
2
3
2
7
2
2
3
6
7
6
9
4
2
2
3
1
1
9
4
1
8
10
1
1
4
1
9
6
2
2
4
1
8
10
5
9
6
3
3
7
2
3
1
6
7
5
5
6
2
7
10
10
10
5...

result:

ok 99979 numbers

Test #18:

score: 0
Accepted
time: 13ms
memory: 4332kb

input:

10 5 99996
2 6
1 6 1
1 8 5
1 7 2
2 5
2 8
2 9
2 7
2 3
2 2
1 2 4
2 2
2 4
1 6 4
2 1
1 6 3
2 2
2 9
1 1 2
2 8
1 1 1
1 5 5
1 3 2
2 8
2 10
2 3
2 6
2 2
2 3
2 5
2 10
2 8
2 7
1 2 3
2 10
1 1 5
2 10
2 1
2 3
2 5
2 7
2 10
1 8 4
2 2
2 7
2 2
2 6
2 8
2 1
2 2
2 8
2 7
2 9
2 1
2 3
2 1
2 6
2 9
2 8
1 4 1
2 3
2 10
2 3
1 4...

output:

6
5
7
8
6
3
2
3
4
1
3
8
7
7
10
4
9
3
4
6
10
7
5
10
10
2
4
6
5
10
1
5
1
8
7
2
1
7
5
9
2
4
2
8
9
7
4
10
4
1
2
7
5
6
3
9
3
10
5
1
4
10
6
8
9
9
7
5
5
10
4
2
9
2
3
8
4
2
7
1
4
6
7
7
5
3
9
9
7
9
6
9
2
2
7
6
5
7
7
6
5
8
7
2
4
10
9
6
7
6
7
3
10
1
4
8
4
7
7
10
5
8
2
9
8
3
9
8
6
9
4
10
10
4
10
10
10
2
8
4
6
3...

result:

ok 99975 numbers

Test #19:

score: 0
Accepted
time: 2ms
memory: 3488kb

input:

10 5 20
1 6 2
2 8
1 8 1
2 7
2 1
2 2
2 4
1 3 5
2 8
2 10
1 7 4
2 2
2 6
2 10
1 4 3
2 2
2 6
1 9 5
2 7
1 3 2

output:

8
6
1
2
4
9
10
2
8
10
2
8
6

result:

ok 13 numbers

Test #20:

score: 0
Accepted
time: 10ms
memory: 4284kb

input:

10 100 99997
1 3 38
2 9
2 9
1 7 44
2 3
2 9
1 3 29
2 7
2 2
2 9
2 3
1 8 58
1 7 19
2 6
2 4
2 8
1 7 71
2 5
2 2
2 6
2 5
2 2
1 4 43
1 5 11
1 4 2
2 5
1 8 50
2 3
1 8 70
2 6
1 4 99
1 4 80
2 3
1 8 74
1 7 77
2 2
1 4 60
1 4 68
2 1
1 6 34
1 5 3
1 7 79
1 5 24
1 2 84
1 9 71
2 8
1 8 27
2 7
1 3 3
1 5 21
2 3
2 5
2 8
...

output:

9
9
4
9
8
2
9
3
6
4
9
5
2
6
5
2
5
3
4
3
2
1
6
7
5
2
6
6
3
8
3
1
10
4
1
7
3
8
4
10
1
2
3
9
1
4
2
6
1
7
2
10
7
3
5
5
7
6
9
7
6
3
1
7
3
6
4
6
4
5
10
6
1
10
4
1
6
3
4
7
1
7
3
6
8
3
3
1
3
9
2
10
5
4
10
5
7
2
4
7
3
5
2
1
3
3
7
7
3
9
7
1
4
4
7
4
10
3
4
4
9
2
6
7
3
9
7
9
6
5
9
9
9
4
5
7
2
2
2
2
5
5
10
1
4
1...

result:

ok 99581 numbers

Test #21:

score: 0
Accepted
time: 13ms
memory: 4324kb

input:

3 5 99995
1 1 2
1 2 4
2 3
2 2
1 2 3
2 2
1 1 1
2 2
2 2
2 1
2 2
2 2
2 2
2 1
2 3
2 2
1 2 5
2 2
2 3
2 3
2 3
2 3
2 2
2 1
2 3
2 1
2 3
2 1
2 3
2 2
2 1
2 3
2 1
2 2
2 2
2 1
2 1
2 1
2 3
2 2
2 3
2 3
2 2
2 1
2 1
2 1
2 2
2 3
2 2
2 2
2 2
2 3
2 3
2 3
2 3
2 1
2 1
2 3
2 2
2 1
2 3
2 3
2 3
2 1
2 3
2 3
2 2
2 3
2 1
2 2
...

output:

2
1
1
2
2
1
2
2
2
1
3
2
3
2
2
2
2
3
1
2
1
2
1
2
3
1
2
1
3
3
1
1
1
2
3
2
2
3
1
1
1
3
2
3
3
3
2
2
2
2
1
1
2
3
1
2
2
2
1
2
2
3
2
1
3
1
1
3
3
1
2
2
1
2
1
1
3
1
1
1
3
1
1
3
1
3
1
1
2
2
1
3
3
1
1
3
3
3
1
3
3
2
3
1
3
1
3
1
2
1
3
3
3
2
1
2
1
3
1
1
1
3
1
1
3
3
2
2
3
2
2
1
2
2
3
1
1
1
2
2
2
1
3
2
2
1
2
3
3
3
...

result:

ok 99990 numbers

Test #22:

score: 0
Accepted
time: 2ms
memory: 3468kb

input:

3 100000 20
1 2 36763
1 2 3289
2 1
1 1 29434
2 2
2 1
1 2 51062
1 1 26892
2 2
1 1 30602
1 1 94867
1 1 23031
2 3
2 3
2 2
2 3
2 2
1 1 28678
1 2 84132
2 3

output:

1
2
3
3
1
1
3
1
3
2

result:

ok 10 numbers

Test #23:

score: 0
Accepted
time: 15ms
memory: 4224kb

input:

10 100 99997
2 4
1 1 72
1 7 26
1 7 43
2 8
1 5 44
2 7
2 9
2 8
1 4 86
1 8 10
1 3 96
1 5 97
1 6 69
1 2 91
2 5
2 6
2 5
1 6 98
1 2 40
1 4 17
1 9 95
2 5
2 8
2 7
1 8 86
1 4 25
1 6 94
1 8 79
2 1
1 9 74
1 1 63
1 9 76
2 7
1 2 29
2 1
2 2
2 9
2 2
2 5
1 3 85
1 1 64
1 2 36
1 5 100
1 6 15
1 5 48
1 1 22
2 10
2 10
2...

output:

4
8
7
9
8
7
3
7
7
10
5
4
6
1
4
8
4
5
9
9
1
8
10
2
1
8
3
9
9
6
9
5
3
9
9
10
10
9
1
6
2
3
6
8
4
1
5
5
3
8
2
10
4
7
3
7
9
6
9
4
3
4
10
5
7
8
8
8
1
2
7
4
7
2
9
9
1
4
9
1
10
4
5
2
5
7
9
9
3
10
5
7
3
5
2
7
5
9
7
2
1
9
2
2
7
3
7
10
2
1
10
10
1
8
4
1
7
5
2
2
2
3
9
9
7
6
9
7
6
10
7
2
5
2
4
8
7
6
10
1
9
10
1
...

result:

ok 99574 numbers

Test #24:

score: 0
Accepted
time: 15ms
memory: 4276kb

input:

10 100 99995
2 2
2 9
2 2
2 2
1 8 88
1 6 21
2 9
2 1
2 5
2 8
1 6 59
1 9 2
2 4
2 10
2 7
1 7 89
2 3
1 7 26
2 2
2 2
2 2
2 7
2 2
2 5
2 4
2 10
1 5 44
2 1
2 8
1 2 76
1 3 55
2 9
2 3
2 6
1 2 86
1 5 99
2 10
2 6
2 5
1 3 19
1 1 38
2 4
2 6
2 10
2 5
1 7 52
1 7 34
2 2
2 3
2 1
2 7
2 2
2 3
2 8
2 10
1 4 57
2 1
1 6 62
...

output:

2
9
2
2
8
1
5
9
4
8
7
3
2
2
2
8
2
5
4
7
1
6
10
4
9
7
9
8
4
9
7
8
1
3
2
6
1
3
5
7
2
6
3
7
10
6
2
4
3
4
5
7
2
9
8
2
4
1
5
6
9
7
7
4
6
6
8
4
1
6
6
7
8
7
4
1
10
8
6
2
7
10
4
10
8
7
7
5
4
1
9
7
3
6
7
4
8
4
6
6
4
6
8
2
6
7
10
2
9
7
1
8
9
3
5
8
4
3
10
8
6
5
3
2
3
2
7
3
8
6
6
8
2
6
6
6
6
10
7
5
7
9
7
8
2
4
...

result:

ok 99576 numbers

Test #25:

score: 0
Accepted
time: 2ms
memory: 3464kb

input:

3 100 20
2 2
2 3
1 2 12
2 3
2 3
1 1 25
2 3
1 2 4
2 2
1 2 87
1 1 32
2 2
2 2
1 1 24
2 2
2 2
2 3
1 2 66
1 1 78
2 2

output:

2
3
2
2
1
1
3
3
1
1
2
3

result:

ok 12 numbers

Test #26:

score: 0
Accepted
time: 2ms
memory: 3348kb

input:

3 100000 20
1 1 59705
2 3
1 1 96861
2 3
1 2 35329
1 2 13432
2 3
1 2 42574
2 1
2 2
2 2
1 2 32127
2 1
2 1
1 1 42623
1 1 83967
2 1
2 1
2 3
2 3

output:

3
3
3
1
3
3
1
1
1
1
3
3

result:

ok 12 numbers

Test #27:

score: 0
Accepted
time: 2ms
memory: 3400kb

input:

3 100 20
1 2 39
2 3
1 1 80
1 2 27
2 3
2 1
2 2
1 1 78
1 1 18
1 2 86
2 1
2 3
2 3
2 3
2 2
2 3
1 2 44
2 3
2 1
1 2 90

output:

2
3
2
1
3
2
2
2
1
2
3
2

result:

ok 12 numbers

Test #28:

score: 0
Accepted
time: 14ms
memory: 4160kb

input:

10 5 99997
1 7 5
2 5
2 4
1 1 3
1 4 3
1 7 4
2 7
1 6 1
2 4
1 2 5
2 5
2 10
1 4 1
2 8
1 9 1
2 4
2 10
2 3
2 7
1 4 2
1 2 1
2 7
1 7 3
2 2
2 2
2 5
2 1
2 10
2 5
2 3
2 4
2 5
2 2
1 5 4
2 7
2 4
2 6
2 1
1 3 4
2 5
2 8
2 9
2 5
2 9
2 3
2 2
2 1
2 8
1 8 2
2 5
2 3
2 5
2 9
2 5
2 6
2 10
2 5
2 9
2 3
2 6
2 6
2 9
2 7
2 8
2...

output:

5
4
7
5
4
10
8
4
9
2
6
6
2
2
4
3
9
4
1
5
4
2
5
6
8
3
2
7
10
2
10
1
4
3
7
2
1
2
10
2
8
7
2
10
1
8
8
10
5
9
7
7
1
5
1
5
10
6
2
6
8
4
2
10
8
9
10
1
1
4
7
5
3
5
5
2
5
2
8
6
10
1
1
6
5
8
8
4
8
8
5
3
1
7
8
9
4
5
6
3
9
5
5
10
2
5
6
5
7
4
8
6
9
9
5
3
4
6
10
4
6
2
4
6
4
9
8
2
3
1
9
10
10
10
10
7
2
4
9
2
7
6
...

result:

ok 99976 numbers

Test #29:

score: 0
Accepted
time: 226ms
memory: 5088kb

input:

10 100000 99997
2 5
1 1 68198
1 6 4509
1 5 74543
1 7 68437
1 8 63663
2 10
2 10
1 4 62195
2 3
1 9 12291
1 3 33708
1 6 65787
2 9
1 3 46161
2 5
1 3 48563
1 8 78539
2 3
2 9
1 5 20498
1 1 98009
2 8
2 4
1 1 97669
2 7
1 1 66304
2 1
1 4 34460
2 2
1 1 89591
2 1
2 6
2 6
2 6
2 3
1 8 75468
1 6 37258
2 10
2 3
2 ...

output:

5
10
10
3
10
4
6
10
8
3
4
1
2
2
5
5
5
4
7
4
1
5
4
6
3
7
6
7
8
6
6
3
6
10
7
10
4
8
5
9
4
4
3
2
2
8
7
5
7
3
10
7
3
8
9
1
4
7
2
6
4
2
8
1
1
7
5
4
8
6
8
3
10
8
4
10
1
5
4
5
1
1
5
7
6
7
9
10
10
1
3
2
10
1
5
4
1
10
2
10
7
3
10
5
2
9
4
4
7
7
9
9
4
7
10
3
7
4
5
3
3
6
4
6
2
7
7
5
2
5
5
10
7
9
7
6
9
3
6
7
4
1...

result:

ok 53532 numbers

Test #30:

score: 0
Accepted
time: 1901ms
memory: 8268kb

input:

100000 100 99997
2 91323
2 51108
1 58111 68
1 23338 77
2 38318
2 10972
1 12004 3
1 72923 96
1 26225 17
2 93537
1 41660 79
1 92069 66
1 20590 2
2 94199
2 51099
2 92961
2 40675
2 68687
1 94317 32
2 94120
2 30949
2 63348
1 84520 32
2 48766
1 59124 59
1 4711 69
2 7426
1 31122 59
2 42307
2 75291
2 78272
...

output:

91323
51108
38318
10972
93537
94199
51099
92961
40675
68687
94120
30949
63348
48766
7426
42307
75291
78272
74285
48367
59905
56503
92353
12192
42050
92571
63868
54374
23917
9044
67248
50093
85566
53790
80793
16557
92611
11853
66385
96749
51504
73710
73601
52923
32697
38197
32655
37582
99555
83324
82...

result:

ok 50427 numbers

Test #31:

score: 0
Accepted
time: 2ms
memory: 3348kb

input:

200 100000 20
1 130 75919
1 58 48816
2 97
1 42 57280
1 143 99525
1 52 55647
2 31
2 19
2 10
2 97
1 179 19505
2 168
1 125 80275
2 112
2 45
2 35
1 36 84431
2 41
2 5
1 146 21446

output:

97
31
19
10
97
168
112
45
35
41
5

result:

ok 11 numbers

Test #32:

score: 0
Accepted
time: 4ms
memory: 3372kb

input:

200 200 444
2 165
2 71
2 84
1 49 199
2 31
2 57
2 165
2 123
1 52 67
2 147
2 80
1 163 138
2 36
2 189
2 74
2 159
1 88 131
2 127
1 198 67
1 31 86
2 77
2 61
2 172
2 15
2 26
1 76 107
1 61 180
1 197 163
2 198
1 35 8
2 177
2 172
2 144
2 189
1 8 171
1 75 93
2 100
2 197
1 86 114
2 46
1 151 13
1 107 145
2 97
2...

output:

165
71
84
31
57
165
123
147
80
36
189
74
159
127
77
61
172
15
26
199
177
172
144
189
100
198
46
97
78
61
172
117
115
107
156
58
119
47
68
84
64
175
25
168
85
12
194
9
184
111
42
93
33
23
6
195
89
180
161
156
67
33
107
14
37
82
156
166
159
123
55
189
86
144
175
73
116
133
120
195
85
89
136
120
129
18...

result:

ok 228 numbers

Test #33:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

200 200 444
1 50 156
2 178
1 115 172
1 19 105
2 15
1 65 80
1 97 10
2 21
2 114
1 61 164
1 110 197
2 189
1 45 183
2 118
1 37 137
1 86 185
2 68
2 38
2 164
2 177
1 141 84
1 63 47
2 16
2 88
2 54
2 46
2 166
1 136 161
2 23
2 161
2 82
1 154 88
2 156
2 183
2 182
2 150
2 37
2 78
1 90 156
2 126
2 178
2 136
2 1...

output:

178
15
21
114
189
118
68
37
164
177
16
88
54
45
166
23
161
82
156
183
182
150
38
78
126
178
137
155
36
185
15
143
173
200
80
25
185
196
160
93
74
18
93
114
179
33
73
49
40
28
93
4
140
177
183
28
115
33
131
42
154
155
179
199
159
34
132
31
178
193
187
156
94
154
176
27
74
107
19
32
42
69
114
9
189
45...

result:

ok 228 numbers

Test #34:

score: 0
Accepted
time: 4ms
memory: 3620kb

input:

5 200 5555
1 2 103
1 3 162
1 3 38
2 5
1 2 145
1 1 90
1 2 147
1 2 107
1 1 75
2 5
1 3 77
2 5
2 1
1 4 93
2 2
2 2
1 4 100
2 5
1 3 121
1 3 73
2 4
1 1 4
2 3
1 1 60
2 4
2 3
1 3 199
2 3
1 2 10
2 5
2 5
1 3 137
2 2
2 4
2 4
2 1
1 1 26
2 5
1 4 108
2 4
1 1 174
2 1
1 3 153
1 3 164
2 5
2 2
1 2 136
1 4 123
1 3 168
...

output:

5
5
5
1
2
2
5
3
4
3
4
3
5
5
2
3
3
4
5
3
5
4
2
2
5
5
3
5
2
4
4
3
4
3
4
5
3
4
1
1
2
5
2
5
4
4
4
2
1
2
5
5
1
2
3
3
5
5
4
2
2
3
1
5
3
2
5
5
2
2
5
1
3
2
4
4
2
4
2
3
3
4
5
2
4
2
3
5
5
3
3
2
5
2
2
1
2
2
4
4
1
5
2
5
5
2
5
3
5
2
1
1
5
3
2
1
1
1
1
5
2
3
4
1
4
1
1
5
2
2
2
5
5
2
4
3
3
4
5
3
3
5
2
2
1
1
4
5
2
1
...

result:

ok 5158 numbers

Test #35:

score: 0
Accepted
time: 3ms
memory: 3476kb

input:

3 99998 444
1 2 86573
1 2 47858
1 2 7363
1 2 4551
1 2 85360
2 3
2 3
2 3
1 1 60369
2 2
1 1 95442
1 1 28660
2 2
2 3
2 2
1 1 95208
1 2 51304
2 1
1 2 24560
2 3
2 3
2 2
1 2 82898
1 2 47967
1 2 24593
2 2
2 3
1 1 34839
2 3
1 1 42124
2 2
2 2
2 3
2 2
2 2
1 1 4830
1 2 4347
1 1 14759
1 2 67945
2 2
2 3
1 2 5506...

output:

2
2
2
3
1
2
1
1
2
2
3
3
1
1
3
3
1
3
3
2
3
2
1
2
2
3
1
2
2
1
1
3
3
2
1
3
1
2
3
1
3
3
2
1
1
3
2
3
3
2
2
1
2
3
2
2
3
2
1
1
2
1
3
1
2
3
1
3
2
3
2
1
2
3
3
1
2
1
3
2
1
2
2
1
2
3
1
3
3
3
3
1
3
3
1
2
3
1
3
2
3
3
3
3
1
2
3
2
3
1
2
1
3
2
2
3
2
2
1
2
3
1
2
1
1
2
2
2
3
2
3
2
2
3
1
2
3
3
2
3
3
1
1
1
2
3
1
1
3
2
...

result:

ok 217 numbers

Test #36:

score: 0
Accepted
time: 114ms
memory: 4664kb

input:

3 99998 66666
1 2 83216
1 1 63804
1 2 48420
2 3
1 2 30485
2 2
1 1 27694
2 2
2 3
2 3
1 2 22881
2 1
2 3
1 1 92867
2 1
2 1
1 2 18779
1 1 62209
1 2 80552
2 1
2 1
2 1
2 3
1 2 15526
1 2 2802
2 1
1 2 15860
2 3
1 2 92264
1 2 22376
2 3
1 2 82784
2 1
1 2 73935
2 2
2 3
1 2 22700
1 2 37392
2 3
2 3
2 2
1 2 49108...

output:

1
1
3
2
2
1
3
2
2
1
1
1
3
1
2
1
1
2
1
2
2
3
2
2
1
2
1
2
2
1
2
2
3
1
3
2
1
3
1
2
2
1
3
2
3
2
2
1
2
2
2
3
3
3
3
3
2
2
2
1
2
1
3
3
3
1
3
3
3
1
3
2
1
1
3
2
3
2
2
2
3
2
1
1
3
1
2
1
2
3
2
2
3
3
3
3
1
1
1
1
2
1
3
2
2
3
1
2
3
3
3
1
2
3
3
2
2
2
1
1
3
3
3
1
1
2
1
1
3
1
2
1
2
2
2
2
3
2
1
3
1
2
2
2
2
2
1
3
3
2
...

result:

ok 38353 numbers

Test #37:

score: 0
Accepted
time: 11ms
memory: 3496kb

input:

3 99998 5555
1 1 17894
1 2 37810
2 1
2 1
2 1
2 3
2 2
1 2 31737
1 1 53853
2 3
2 2
1 1 28771
2 1
2 1
1 1 31845
1 1 86225
2 1
1 2 65732
1 1 6390
1 2 56602
1 2 44026
1 2 18330
1 1 34750
2 3
1 1 77984
1 1 5571
2 3
1 2 89815
1 2 63607
2 1
1 1 23160
1 2 94025
2 1
1 2 19803
2 2
2 1
2 2
2 3
1 2 32407
2 1
2 3...

output:

3
3
3
2
1
3
2
2
2
3
1
2
1
1
3
2
3
1
3
1
3
1
2
1
2
1
2
1
2
2
3
2
3
2
1
1
2
1
3
1
1
3
2
2
2
3
1
3
3
2
2
1
2
3
2
3
3
2
3
1
2
1
2
2
3
1
3
2
2
1
1
3
2
3
1
2
1
3
2
1
3
1
2
3
2
3
3
3
2
3
3
3
2
3
3
2
1
2
1
3
1
1
3
1
1
3
2
3
1
3
3
3
3
3
1
1
2
3
3
1
3
2
1
3
1
3
2
2
2
1
3
1
2
2
2
3
3
2
3
1
3
3
1
3
3
1
2
3
2
2
...

result:

ok 2837 numbers

Test #38:

score: 0
Accepted
time: 335ms
memory: 5408kb

input:

50 99997 100000
2 15
2 1
1 5 460
2 16
2 33
1 26 22817
1 32 57730
1 12 49344
2 24
1 48 78596
1 2 4273
2 2
1 31 92410
1 18 11945
2 22
2 3
1 2 47838
1 5 66084
1 3 51032
2 48
1 3 73823
2 11
1 44 69177
2 41
1 3 67803
1 1 41983
2 29
1 5 4984
1 3 14926
1 1 19550
1 4 23996
2 2
1 2 55552
2 9
2 41
2 13
1 20 1...

output:

15
1
16
33
24
3
22
2
49
11
41
29
6
9
41
12
25
25
21
11
34
2
26
20
21
1
1
5
23
48
17
7
34
7
25
15
38
43
28
47
40
49
42
29
24
34
47
15
29
40
9
1
13
33
31
47
15
49
20
32
14
14
29
22
21
45
46
41
13
7
23
47
44
47
48
40
9
50
20
25
34
6
41
24
19
11
36
33
37
18
17
30
5
36
10
30
34
28
34
1
9
49
11
47
18
17
1...

result:

ok 51923 numbers

Test #39:

score: 0
Accepted
time: 337ms
memory: 5260kb

input:

50 99997 100000
1 5 91754
2 31
1 5 49396
2 37
2 1
1 2 49833
2 1
2 32
1 36 58423
2 36
2 48
1 48 57743
1 44 13519
1 3 34770
2 25
2 18
1 33 4593
2 28
2 24
1 1 89841
1 18 16369
1 1 86567
1 3 21985
2 23
2 18
1 39 21575
1 4 885
1 30 9434
1 26 82438
2 35
1 5 74679
2 47
1 10 49171
2 11
2 32
1 6 58414
2 4
1 ...

output:

31
37
1
1
32
37
48
25
18
28
24
23
19
35
47
10
32
7
23
46
20
18
7
24
45
5
28
18
30
26
40
10
38
46
39
40
5
31
21
6
35
38
11
36
15
23
9
41
42
18
8
49
15
22
27
2
37
41
28
28
9
10
2
12
10
44
32
47
28
42
28
1
30
24
18
48
7
39
16
44
19
19
29
50
31
13
23
19
37
9
10
4
17
8
40
1
31
48
42
38
16
39
20
2
33
12
2...

result:

ok 52287 numbers

Test #40:

score: 0
Accepted
time: 351ms
memory: 5344kb

input:

50 99997 100000
2 28
2 43
1 2 37572
2 17
1 16 22203
1 5 28006
1 3 69631
2 50
2 39
2 31
1 33 52184
2 48
1 2 88889
2 37
1 3 54786
1 2 89816
1 2 61584
1 2 1804
1 1 46769
1 5 50489
2 44
1 3 49339
1 40 18496
2 43
2 49
2 50
2 45
1 40 56707
2 38
2 50
1 23 84774
2 42
2 18
1 1 24812
2 22
1 24 55916
1 9 60712...

output:

28
43
17
50
39
31
48
37
44
43
49
50
45
38
50
42
18
22
43
49
25
32
45
47
13
27
25
32
34
17
47
17
35
6
18
42
10
6
19
24
42
12
31
14
6
7
34
7
16
44
35
47
31
41
48
48
21
11
24
27
33
20
42
28
15
20
1
28
1
9
50
6
43
1
30
29
49
16
16
32
6
23
1
31
41
48
45
44
31
20
18
20
2
10
26
30
39
27
46
11
26
22
23
18
2...

result:

ok 51939 numbers

Test #41:

score: 0
Accepted
time: 340ms
memory: 5492kb

input:

50 99997 100000
1 33 68534
2 47
2 45
1 32 728
2 48
1 4 92826
2 1
2 46
2 24
1 5 77867
1 5 81166
1 12 61775
2 48
2 21
1 16 2654
1 5 41711
2 37
2 24
2 2
1 1 95552
2 12
1 2 50935
2 48
1 3 22987
1 1 745
2 48
2 6
1 2 82254
2 4
1 3 73148
1 2 58653
2 8
1 28 60585
2 42
1 41 6721
1 41 61606
1 2 89435
2 43
2 3...

output:

47
45
48
1
46
24
48
21
37
24
2
13
48
48
4
3
8
42
43
31
7
29
10
44
17
8
43
15
7
8
18
39
26
39
35
43
20
22
31
3
39
26
28
1
42
8
27
30
7
17
10
46
39
40
6
33
31
30
21
8
12
29
10
9
39
46
49
47
3
2
19
43
1
7
33
29
9
16
48
18
37
23
22
40
13
45
47
32
34
21
36
49
29
25
30
19
47
32
34
49
18
12
9
20
18
36
35
2...

result:

ok 51759 numbers
English 繁體中文 简体中文

Server Time: 2024-12-02 16:51:57 | OpenSource Project