TEST DATA FOR `lazy'

Input for test 1

8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4

Output for test 1

10

Input for test 2

6 2 100
1 1
1 2
1 3
2 2
2 3
2 4

Output for test 2

6

Input for test 3

6 1 100
1 1
1 2
1 3
2 2
2 3
2 4

Output for test 3

8

Input for test 4

100 10 100000
2 51052
2 98443
2 66949
2 49783
2 34762
2 48009
2 66717
2 54681
2 45563
2 86013
2 74165
2 25782
2 36504
2 44958
2 96130
2 64622
2 89476
2 89573
2 95423
2 42344
2 99737
2 1470
2 18004
2 52036
2 75946
2 30790
2 37545
2 97469
2 35219
2 47198
2 36377
2 20936
2 96490
2 57312
2 26103
2 66149
2 13156
2 74410
2 95221
2 38912
2 69485
2 3850
2 24005
2 90430
2 64296
2 31541
2 55283
2 62804
2 13811
2 7949
2 43977
2 6373
2 85062
2 11508
2 53772
2 66789
2 96658
2 28976
2 20776
2 71911
2 99010
2 85804
2 59583
2 99350
2 12499
2 31278
2 44899
2 58406
2 82958
2 31526
2 35832
2 49861
2 32929
2 74946
2 12569
2 29827
2 49563
2 14490
2 65162
2 89266
2 9840
2 41754
2 23247
2 1509
2 47928
2 61550
2 42055
2 54327
2 8327
2 71403
2 52459
2 32734
2 15183
2 25069
2 32789
2 49820
2 67294
2 89582
2 74305
2 89955

Output for test 4

67049

Input for test 5

10 3 100
1 1
1 2
1 3
1 6
1 7
1 8
2 3
2 4
2 6
2 7

Output for test 5

11

Input for test 6

99 99 1000000
2 996175
1 455803
1 106457
2 853751
2 350919
2 93554
1 370848
2 729954
2 208148
1 995614
2 266849
2 371154
1 182769
1 955896
1 953481
2 639955
1 481215
2 357189
1 960397
1 384241
1 940757
1 611567
1 73559
2 456762
1 425439
1 18079
1 259930
2 716839
2 545228
2 982075
2 367796
2 60587
1 400307
2 252461
1 590279
1 378630
1 69059
2 76316
2 711857
2 224041
2 856116
2 944737
1 971177
2 888292
2 895974
1 909431
2 968163
1 529298
2 568008
2 286496
2 419402
1 973155
1 320333
1 931978
1 723030
2 819983
2 922802
2 173244
1 232804
2 524303
1 873540
1 910819
1 860765
2 191697
1 668766
1 367308
1 128901
1 935999
1 912232
2 453139
1 72411
2 775086
1 788512
1 743317
2 460677
2 208368
2 253405
1 615001
2 646765
2 815352
1 405143
2 182679
2 982242
2 442221
1 891629
2 285833
2 141349
2 802125
1 881828
1 933439
2 887020
2 604946
1 83518
1 290272
1 780978
1 653588
2 524950
1 501947
2 91116

Output for test 6

99

Input for test 7

250 100 15000000
2 2448898
1 9843453
2 3533600
1 4813041
2 11860279
1 2218657
2 9396574
1 13598307
1 4824419
2 9773399
2 2486710
2 10661400
1 9213950
2 4169585
2 7438261
1 7304200
1 9316
1 1812874
2 11312608
1 11963715
1 10278997
1 6474485
2 8524055
2 7771558
2 9182
2 10672137
1 8850893
2 12345081
2 7281624
1 9975609
2 4580767
1 10506414
1 7328713
2 10081149
2 1604043
2 13413760
2 243802
2 10146375
2 9752256
2 846119
2 12592612
2 2493569
1 4880888
1 12108222
1 6858052
1 3374190
1 4116595
1 5216756
1 5556079
1 7041170
1 11328687
2 3692087
2 3984228
2 897993
2 12243024
1 411494
1 1907230
2 12984788
1 2693668
1 3580531
2 45657
1 4521619
2 14303529
1 10948461
1 2013793
2 4657871
1 4399858
1 14931784
2 6351977
2 6974074
2 6203892
1 8316749
2 11516421
1 2648752
2 6286057
2 7687283
2 9126017
2 8537811
1 3949054
1 9669133
1 2420972
1 9717710
1 11590806
1 8494103
1 2762054
1 316114
2 1207634
1 12270093
2 12092089
2 8694938
1 25172
2 14693232
1 13592804
1 3260664
1 12790453
2 3757750
2 11300433
1 13355494
1 14523215
1 4307301
2 2192487
1 830403
1 10507902
1 7028294
1 1225909
1 12017337
2 9969
1 2711367
1 993299
2 11902769
1 11620997
2 2301503
1 8069232
1 7358545
1 1276786
1 5420318
2 7742652
1 14308408
2 13850970
2 7675950
1 7674167
2 14699795
1 10803879
1 10176522
1 14078512
1 3110460
1 14662230
2 3232488
2 11312805
2 4748216
1 6119921
2 10271299
1 12250183
2 6499495
1 11283558
2 2494601
2 7536197
2 5548697
2 38533
1 14783812
2 6761887
1 5925213
1 1682345
1 8804235
1 13742704
2 12138746
2 5861502
1 170968
1 1466476
1 10835993
2 10456761
2 2921677
1 14866409
2 1152997
2 3388590
2 1391931
2 11386614
1 2147381
1 2360655
1 6908089
2 5337920
1 6373458
2 10323756
2 14500834
1 2290795
1 2310613
2 14926066
2 3099299
1 9219918
2 4971589
1 7417651
1 1391282
1 9801515
2 8602277
2 5398160
1 729422
2 2169804
2 12938307
2 9436221
2 6126250
2 3562961
1 10006193
1 5947464
2 6512921
1 7631757
1 11948020
2 7795269
1 6036955
1 10745546
2 11808605
1 14874207
1 4243701
2 13410585
1 8652763
1 9450805
2 9524310
1 11914645
2 10777802
2 269655
1 7219815
2 3529686
2 6152554
2 10385055
1 1246546
2 11040873
1 2549224
1 6349239
1 11052397
2 14025474
1 1138044
2 777935
2 14126593
2 10179243
1 1587183
1 11422352
2 8167397
2 5080607
2 3951571
2 12703875
2 11362824
2 13094555
1 12844267
1 213644
1 4058729
2 5648369
2 7562692
2 14943802
2 376748
1 5860357
2 2989535
2 12000665
2 9101403
1 470550
1 204315
2 3252143
2 9381242
1 1208817
1 12826594
2 4782693
2 13483264
2 8141149
2 165490
1 8168699
2 11002929
1 12158862
1 1272645
1 9445598
2 1563903
1 7618275
2 4986986

Output for test 7

6176566

Input for test 8

15 3 1000
1 17
1 50
1 159
1 249
1 291
1 381
1 653
1 779
1 820
1 881
1 990
2 185
2 325
2 499
2 502

Output for test 8

1021

Input for test 9

20 3 100000
2 25782
2 34762
2 36504
2 42344
2 44958
2 45563
2 48009
2 49783
2 51052
2 54681
2 64622
2 66717
2 66949
2 74165
2 86013
2 89476
2 89573
2 95423
2 96130
2 98443

Output for test 9

50875

Input for test 10

1000 850 15000000
2 2143372
1 1354059
2 9217098
2 119299
1 12878178
1 5500506
1 4034804
2 5611202
2 10123461
1 2145953
1 7446701
2 2509911
1 2523720
2 4974782
2 13986104
1 3120496
2 13558314
2 10005461
2 8848319
1 7793798
1 6662317
1 12977974
1 3207067
1 8501532
1 10696810
2 3000387
1 10116165
1 7143049
1 10267365
2 6620034
1 2045526
1 4279996
2 1419743
2 12163548
1 14865144
1 1783237
1 13490842
2 12837392
1 8574173
2 1133205
1 7360728
2 13696773
2 7274325
2 7840456
2 4038084
1 2175782
2 14807727
2 6647522
2 416688
1 14425316
2 3119019
2 6836258
2 11164575
1 227779
1 2759884
2 2096704
2 12050275
1 12748806
1 9031318
1 5014068
2 5572085
2 10846170
2 13054903
2 2299784
1 9536565
2 1084799
2 9578925
2 8430673
1 13231508
1 9004222
2 2558647
2 7367071
2 14056375
1 14551045
2 502131
2 9496386
2 4909739
1 9923964
1 6243954
2 3892866
2 9288534
1 9382557
1 198778
2 9397462
1 11927934
2 14843567
2 12255150
2 11903490
2 2903472
1 3329570
2 5297046
2 14584389
2 7428504
1 12544913
1 12886577
1 12619219
1 7110448
2 14032498
1 9905923
1 9259608
1 11178172
2 9512456
1 7939959
1 838707
2 8160779
2 10119971
1 1883183
2 14548296
1 9684453
2 5344460
2 10675458
2 4504512
2 13459402
1 3526046
2 3210728
2 3785776
1 7152886
2 13787708
2 5321262
2 7758298
2 13687121
1 10272697
1 317136
1 2105164
2 1562381
1 8516791
2 3856554
2 2544318
2 1085874
1 713657
2 3937258
1 12258840
2 13885998
1 6529040
1 8532693
1 7569776
2 8809372
2 8985734
1 1848702
1 12357338
2 2234526
2 10776233
2 5347471
1 2180644
2 4991452
1 5163669
2 6575059
1 4959249
2 6450195
2 2404134
2 12437262
1 11461549
1 3934481
1 7364640
1 13895703
1 10695736
2 2427863
2 11720990
2 1101938
2 12618309
2 10570166
1 14798509
1 6752021
2 8363240
1 14191029
1 766050
2 5927369
1 11451716
2 3095102
2 6509907
1 7889904
1 7167989
1 500006
2 14099228
1 9220369
2 11481164
1 12433409
1 14308232
1 8328349
1 5555891
2 11519611
1 8182980
1 13720920
2 7026707
2 928805
2 12131686
2 7494022
2 14811411
2 4823698
1 3477502
1 1306524
2 308153
1 11418446
2 12841410
1 14611612
1 14359023
2 3763899
2 7120344
1 4153529
2 1369770
1 11590893
2 2191841
2 14689833
1 9450828
1 9979895
1 12811522
1 8570260
1 3389220
2 2280530
1 3473363
1 11192903
1 5673942
2 578579
2 13275235
1 466820
2 4679297
2 2100802
1 73355
1 6237366
1 3461235
1 14259445
2 9419272
2 176380
2 2441065
2 4568595
2 1951733
1 7904075
2 14539024
1 4413544
2 4063205
2 13092821
1 7077001
1 7622106
2 5777072
2 8005199
1 995309
1 10973362
1 1856466
2 6339569
2 9622729
2 9184560
2 7219406
2 12396087
2 1402148
1 6540955
1 10757393
1 10434449
2 3605930
1 1176102
2 2645796
2 14671841
1 7175762
1 6071688
2 14194348
2 13665433
2 1391041
2 13126214
1 11214770
1 2838433
2 11107968
1 13140913
2 6779998
1 10642091
1 3818324
2 5289003
1 2115715
1 2298214
1 8752533
2 9570955
2 10199841
2 237623
2 5695897
2 14913699
1 5449325
2 12239667
2 7100033
2 3945710
2 4646097
1 1886280
2 3453326
2 3072712
2 13995189
2 11271224
2 8724832
1 8290241
2 14918030
2 12951057
1 5015382
2 8199588
2 6862629
1 1889025
2 3337747
1 10942680
1 9059808
2 13626462
2 704524
1 1239203
2 9770863
2 7118429
1 2428021
2 2395811
2 6157001
1 9591238
2 7730745
1 11062555
2 5454597
2 11419140
2 6428174
2 9635645
1 13662792
2 1375859
1 4577342
2 12548480
1 6441141
2 6693797
2 7585343
1 8254365
1 3375014
2 13159658
2 10341211
1 3484641
2 6195134
1 7989845
1 472691
2 5364952
1 3935099
1 2462423
2 12836279
1 10190146
1 8376986
1 12234565
1 5824491
2 5094866
1 1470025
1 945306
1 8018635
1 5512112
2 7711116
1 12093077
2 12128474
1 7186102
1 3748368
2 285889
2 12041986
2 11598553
1 9710083
2 789182
1 13159025
2 12978975
1 11971548
1 842259
1 1002006
2 3599906
2 250719
2 12478872
2 8384842
2 1806981
2 8071354
2 14570916
1 7178188
1 14201553
2 4748329
1 6516355
1 1934628
1 9580068
1 9134863
2 12413378
2 4331788
2 2639686
1 5425084
1 7702451
1 9554432
1 10083673
1 4327815
1 5116322
2 13368450
2 602841
2 13918675
2 3355181
1 11740212
2 8270854
1 13437571
2 200088
1 8424114
1 1171474
1 227332
1 1792408
1 4979228
2 8574877
1 14906728
1 1540419
2 2182790
2 5697890
2 12737311
1 566377
2 6783859
2 5019585
2 4978485
1 11778254
1 2984811
2 2278889
1 2828918
1 6539979
1 8951423
2 8654912
2 3324865
2 1522435
2 5034129
2 13223479
2 11307195
2 13644606
1 12233616
1 11594860
1 4278872
2 8060160
1 11763281
2 7667968
1 12653332
2 12909418
2 9349137
1 685317
1 11541695
2 5040034
2 6164591
2 4240822
1 6842923
2 8101889
1 12023125
1 2579020
2 12986032
2 13342565
2 10646219
2 2429591
2 7227142
2 14069455
2 11486967
1 10745046
2 10926645
2 12102927
2 7721644
2 52281
1 11722945
2 3622120
2 5622101
1 8690142
2 1979229
2 7600868
1 6591174
1 12985493
1 3308383
1 12545860
2 4681388
1 7419257
1 14378695
2 6482575
1 4424084
2 2051681
1 14569126
2 1086667
1 6271655
1 3912619
2 14377958
2 3529360
1 14899960
1 5717875
2 9792288
1 3995087
2 9031000
1 11146688
1 7098323
2 7937996
1 10317865
2 1008210
1 1853647
2 9971072
2 3184457
1 13936344
1 952563
2 827566
1 2331902
1 8782602
2 14894359
2 5099024
2 14911608
1 8625641
1 3511787
1 5437649
1 10121773
1 3283923
2 2533252
1 3612841
2 209743
2 3404480
1 10437188
2 5232693
2 13556936
2 14606004
1 110793
1 13080832
1 2686156
1 9778543
1 12847758
1 3877429
2 7662939
1 6484831
1 13210839
2 4850331
2 3463171
1 14469824
1 7245085
2 14798156
1 8448542
2 565258
2 3456238
1 9341870
2 5129501
2 14775114
2 10866293
1 11794744
1 13902201
1 7045590
1 6324397
2 9532729
2 10421515
2 9159770
2 14086256
1 10918210
1 2716529
2 352380
1 14478902
1 14719732
2 10068031
1 3614122
2 240149
2 7578690
1 12049308
1 2247779
1 13863279
2 10401123
1 7982204
1 8049859
1 1987444
1 6598671
2 9379661
2 8521793
1 8553001
2 8867359
2 10734125
1 763733
2 2088447
2 11676318
1 12267968
2 9171773
2 9111826
2 8840673
1 1987707
2 7745930
2 214462
1 9473731
1 13578124
1 10721504
2 7948558
1 6253253
1 1335462
2 12360455
1 1162678
2 2294999
2 8470736
2 3082214
2 13920336
1 7003867
1 10714760
1 14674859
1 13596876
2 12068866
1 3225841
2 12107866
1 12178533
2 11282791
2 339165
2 8466676
2 2185047
2 12100879
1 9703755
2 7747068
1 4003368
1 2804878
1 14828437
1 7683891
1 9755016
2 1809840
2 3002630
1 11443938
1 123310
2 10040617
2 3970800
2 2886797
2 9839167
1 8413426
1 3621329
2 190284
1 9765396
2 10285011
1 6301064
1 1948575
2 13729351
2 13277800
2 14186201
2 3381432
2 11432519
2 6154143
2 12428206
2 13041954
2 14913097
2 14396077
2 9550350
2 12378041
2 153812
1 7849245
2 8795979
1 11689280
1 2512188
2 5210469
2 2824005
2 1426265
2 14704205
1 3278137
1 1310181
2 12403343
2 9094719
2 13742972
1 3644562
2 2338589
1 7039256
1 1873868
1 2016133
1 9196314
2 11981726
2 4749424
1 3744919
2 14087694
1 4941342
2 1700403
2 10760003
1 2984124
2 5919463
1 6361786
2 8628672
2 12215688
2 2623310
1 3185207
2 12517536
2 7663634
1 13738453
2 1433482
2 2910781
2 11711051
2 7785687
2 1568559
2 14823801
2 5389937
1 370372
1 12552655
2 10632302
1 5755636
2 2373522
1 13909451
1 3487548
1 5331147
2 4343885
2 3438165
1 10607761
2 11494070
1 13028983
1 5237907
2 13523762
1 3927996
1 9630516
2 3183191
2 10613789
2 7727895
2 10985776
1 2193568
2 5988012
2 8435610
1 14461646
2 8561267
2 2977586
1 3186806
2 9901499
1 11240393
2 10146191
1 4274784
2 7487743
2 3359598
2 7873827
1 12779306
2 13874011
2 7297312
2 4163231
1 5470119
2 400897
1 2454513
2 9388598
2 7975151
2 11637920
1 7374671
1 1244406
2 1202346
1 14891781
1 2093875
1 13158949
2 1221902
2 6687278
2 7556333
1 1912789
2 5252196
1 562106
1 6601314
2 8146666
1 8047943
2 1820577
2 417249
2 1856486
1 13863161
2 9163679
2 5467116
2 8854857
2 9254311
2 10354144
1 8716372
1 8529217
1 11300465
1 9285158
2 3540609
2 13045933
1 9347664
2 5000024
1 14954735
1 8437853
1 1133627
2 4357589
2 788903
2 13769597
2 6116757
1 4154442
2 138552
2 10800498
2 19924
1 10599822
2 1836809
2 13259412
1 5004741
2 4092953
2 8837175
2 12008705
2 9516124
2 10274904
2 4252796
1 5006571
2 5679654
1 9318353
1 11375764
2 14077425
2 195814
1 14378542
1 8295827
2 14069424
1 11955431
1 12057459
1 12752489
1 9016287
2 6099681
2 12630722
2 4587909
2 4427401
1 14965787
2 652849
1 6620147
2 9805792
1 11296077
1 12391588
1 4927212
1 5937880
2 8243307
2 5345648
2 6421993
1 2412016
2 4079227
1 11872670
1 5206590
1 7204632
1 7106096
2 13695468
2 14521663
2 12023435
2 8082407
2 11764547
1 13152363
2 4416407
2 3504331
1 11633582
1 3917019
2 443434
2 8333447
1 8152061
2 7348183
2 14964277
2 1229049
1 4895435
1 5877757
1 5322119
1 9029901
2 3338148
1 12758849
1 3396316
1 10135531
1 14328577
1 10596631
2 5661019
2 13561224
1 14947401
2 1718896
1 1018212
1 1783610
1 12322127
1 6694126
2 6774261
2 6055300
2 7430447
2 8100818
1 14198417
2 12647260
2 11353838
2 9166433
2 1639831
2 2476675
1 3840237
1 6127754
2 10186410
2 14795799
2 9400885
1 4116567
1 9324500
1 3053820
1 9501343
1 9045496
1 3002678
2 2699056
2 10710442
1 12358466
1 4916010
1 11562786
1 12943348
1 6618648
2 10709016
1 13558846
2 14176165
1 12733927
2 9146120
2 5744584
1 3219440
2 9165788
2 4117719
1 12319093
1 316660
2 9732206
2 9638105
1 1883635
2 6481280
2 4598480
2 748277
1 11256945
2 11602035
1 8752145
1 4462297
1 324642
2 13431260
1 13678965
1 11590163
1 2807230
1 4624631
2 11096653
1 12433262
1 7455212
2 3023229
1 12461398
2 1980302
1 8022591
1 11360018
2 9539390
2 3332212
2 3431589
1 1532791
2 4631448
1 1653822
2 6821646
2 10514368
2 14053510
2 4988243
1 13674829
2 14868263
2 5209129
1 7776675
2 14927517
2 8704272
1 6042283
1 2901989
1 10914771
1 5743384
1 829688
1 3518727
2 6149074
1 9965120
2 8161463
2 1845295
2 8309134
2 1082886
1 567403
2 13475908
1 12407228
2 5834121
2 10573229
2 7620489
1 2915096
2 13781990
1 10017135
1 1000009
1 2658632
1 2004067
1 8221551
1 5912864
1 2540701
2 6690954
1 5098470
2 1244738
1 619121
2 11293927
2 2468826
2 3919944
1 12753421
1 10445743
2 797305
1 2486610
2 4939239
1 6432369
1 4183624
1 9191148
1 14573234
2 515926
2 13809713
2 7029271
1 14234201
1 9900304
2 4119382
2 3861430
1 12127552
2 12590889
1 6802938
1 1749856
1 13120629
1 6828546
1 173907
2 6212497
1 8295348
1 4175464
1 10758355
1 7095965
1 4162400
2 696678
1 9869513
2 245195
1 10117822
2 9016055
1 10611251
2 2091858
1 9377966
2 10329219
1 143647
1 12696657
1 4502954
1 9728375
1 8152256
1 6662458
1 13711473
2 5435192
2 289846
2 5685815
2 13501276
1 7747862
1 4905283
1 6333762
1 6620036
2 6687176
1 7638862
2 6920852
1 12180232
1 8473896
1 11446808
1 8118242

Output for test 10

257587