Milk Tea Quality Queries

Points: 100

Time limit: 2.0s

Memory limit: 256M

Author:

Problem types

There are 200,000 cup positions, initially with zero sugar. Each of \(N\) operations adds one gram to every cup in an inclusive range. A cup qualifies if it has at least \(K\) grams. Answer how many qualifying cups lie in each query range.

Input

The first line contains \(N,K,Q\). The next \(N\) lines contain operation ranges \(L,R\). The next \(Q\) lines contain query ranges \(L,R\). All positions are one-based.

The input satisfies:

\(1 \le K \le N \le 2 * 10^5\)
\(1 \le Q \le 2 * 10^5\)
\(1 \le L \le R \le 2 * 10^5\)

Output

Print the number of qualifying cups in every query range.

Example

Input

19 10 357
180690 190294
58576 94114
96683 143440
109392 187724
73229 157785
108347 117297
28079 94207
181761 194697
91312 111956
52300 82127
28050 99217
10212 48845
5844 163931
16720 196494
102402 126014
2540 193785
91673 145752
15313 70270
87734 176405
157777 161829
13766 114395
177017 195255
100952 146677
174246 196706
33594 34818
122645 150434
153326 194742
149547 187900
157227 188679
68651 106443
152780 186234
134999 192671
179187 188280
151377 184467
119564 169297
4214 77538
82021 167472
48524 184912
10947 91356
106975 194017
78643 185303
61316 102396
47589 106472
24182 189145
60639 187754
96317 144476
107601 146920
85090 115627
115896 176310
140190 148514
38283 174243
151936 176745
151392 198145
133170 198307
26083 134954
122659 142850
81767 156785
65733 80146
44492 133823
114650 123989
95987 185168
116618 198959
13697 22149
123146 175884
190750 197667
103711 197666
165229 185604
17907 149267
60296 175132
5103 92019
195092 199597
157909 183596
18632 140819
179888 193492
199323 199395
25908 84046
183332 191226
150680 172993
57996 185937
65116 169427
112880 162643
165468 166694
31939 163620
35772 103205
119110 143213
64662 196509
26350 152756
46783 85059
73614 95819
41087 160973
52463 165064
110765 112698
90706 127296
78699 159546
24538 171852
28285 86193
59089 196796
57910 168336
76354 118275
176021 188439
111262 179539
164545 171381
167441 193935
90589 155122
29798 35151
52872 163738
5499 125804
124388 126215
148960 164466
56006 184038
82601 92845
182055 187299
35758 91185
130234 165356
104677 167865
183055 191780
134787 137723
123100 195193
174661 194954
148325 159431
39901 126753
89975 90295
123270 166041
27831 142946
170449 196310
159794 191271
90954 94751
16012 30985
89489 154898
155475 156739
159910 199873
51750 126473
20927 94374
11417 175353
12496 62328
22247 47905
178250 188279
78664 140933
156609 177705
40282 144483
99679 128638
169341 183555
150740 163195
195514 199933
179428 190933
143149 172547
93759 114571
123634 161383
180553 188159
188954 197370
35182 98103
169298 182628
31770 177269
133017 166795
178457 196529
19458 162753
60486 61306
191578 199141
8461 142191
94220 188535
36355 139114
48142 193958
133940 194646
21198 123335
42282 169737
76453 142917
129757 144910
53982 79082
118034 120859
15317 87248
112505 141518
186258 188509
45254 104484
20976 35981
148532 182253
78854 188734
7105 55381
107876 151749
46771 55458
146587 181965
141555 156350
51641 119288
5804 9969
85903 142000
199569 199974
136048 164680
49671 97677
85831 146452
158235 197840
1075 148153
128194 198813
197661 198321
27433 190712
38322 50026
142050 142448
179886 187690
23415 33114
58098 116761
125886 171491
74809 102825
113155 198581
22206 45606
36515 39666
182761 186046
125230 149187
124316 133693
141449 183882
25019 91280
5447 97103
114672 144946
46544 68631
103336 122915
191790 196315
114304 156906
140696 199959
169438 182506
61049 158305
51971 94065
108249 145043
67834 114463
82895 180057
136309 172412
47925 124088
163827 184356
93749 105448
193347 195424
102225 157329
49024 135545
125178 182177
93350 161361
126860 145459
56378 58295
70200 105217
171420 177380
40107 117028
175874 179283
83516 136376
115754 164398
40832 124545
48664 149106
18539 162315
13552 181992
22057 36429
169158 185438
163639 171001
159663 187575
87765 160584
71676 179547
144854 145877
198664 199173
65321 188030
126113 178903
9504 39006
7633 118467
173786 190518
14263 143227
3986 173164
166426 167388
127108 187807
54368 197246
152741 179322
18119 98773
148151 193316
51138 105172
19593 145703
99245 174527
51948 106707
32455 162336
182238 196793
124189 174487
17648 125078
87179 149604
191993 196437
128020 175897
65585 179583
80716 96224
114305 166170
65640 115281
130825 152738
53206 93894
117256 146370
118757 161913
129372 175997
125610 182348
151801 156946
140251 197087
65790 80310
189967 196727
67247 159649
11379 74054
142156 188498
183617 192632
151006 188740
165885 190363
115024 197861
47963 122935
75000 162922
50777 59253
91495 133417
152512 161514
112110 195137
1872 156532
12606 81678
119896 159413
149595 182073
195866 199734
191342 195722
62764 137747
80172 85229
184743 191828
111942 131314
116302 167112
164115 195559
26093 187536
46224 72725
84030 139375
136489 145425
18731 172425
93994 163309
53731 196751
162815 183833
134698 178042
126133 136887
132275 184057
122239 176599
68655 134038
80838 179734
63578 171627
117216 121338
199963 199983
33866 134594
121599 195975
67298 82691
13827 113406
79909 145105
94643 168359
78926 116084
82254 112257
114489 188922
93220 138882
199520 199583
123176 129465
13829 137592
152845 191895
40663 77088
5321 58457
41470 101504
6045 185423
29532 84701
199408 199612
187878 196334
123985 136341
93006 106975
72806 193555
13791 67621
176444 193628
198167 199498
123375 184037
87653 116107
179769 197509
126061 194245
14260 124031
102003 190482
46968 162250
37810 161468
36086 90716
11841 31905
102759 155391
188785 195379
140204 198151
162964 165464
60563 98264
153202 196059
194925 199714
100612 199778
155969 172224

Output

Comments

There are no comments at the moment.