QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#403369#1286. Ternary String CountinglifanAC ✓587ms199448kbC++141.9kb2024-05-02 09:37:412024-05-02 09:37:42

Judging History

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

  • [2024-05-02 09:37:42]
  • 评测
  • 测评结果:AC
  • 用时:587ms
  • 内存:199448kb
  • [2024-05-02 09:37:41]
  • 提交

answer

// 
#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;
int T,n,m,v2[50003][2],v3[50003][2],k1,k2,k3,k4,k5,k6,k7,k8,k9,ans;
int dp[5003][5003],hsum[5003],lsum[5003];
int q[100003],lft,rgt,zz[50003];
void del(int X){
	for(int i=0;i<=X-1;i++){
		if(i>=v3[X][0]&&i<=v3[X][1])continue;
		if(i==X-1&&i!=0)continue;
		hsum[i]=0;
		while(zz[i]<X){
			lsum[zz[i]]=(lsum[zz[i]]-dp[i][zz[i]])%MOD;
			dp[i][zz[i]]=0;
			zz[i]++;
		}
	}
	while(lft<=rgt){
		if(q[lft]>=v2[X][0])break;
		lsum[q[lft]]=0;
		for(int j=0;j<=n;j++){
			hsum[j]=(hsum[j]-dp[j][q[lft]])%MOD;
			dp[j][q[lft]]=0;
		}
		lft++;
	}
	while(lft<=rgt){
		if(q[rgt]<=v2[X][1])break;
		lsum[q[rgt]]=0;
		for(int j=0;j<=n;j++){
			hsum[j]=(hsum[j]-dp[j][q[rgt]])%MOD;
			dp[j][q[rgt]]=0;
		}
		rgt--;
	}
	return;
}
void add(int X,int Y,int val){
	hsum[X]=(hsum[X]+val)%MOD;
	lsum[Y]=(lsum[Y]+val)%MOD;
	dp[X][Y]=(dp[X][Y]+val)%MOD;
	return;
}
int stk[50003];
void sol(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		v3[i][0]=v2[i][0]=0;
		v3[i][1]=v2[i][1]=i+1;
	}
	for(int i=1;i<=m;i++){
		cin>>k1>>k2>>k3;
		if(k3==1)v2[k2][1]=min(v2[k2][1],k1-1);
		if(k3==2){
			v2[k2][0]=max(v2[k2][0],k1);
			v3[k2][1]=min(v3[k2][1],k1-1);
		}
		if(k3==3)v3[k2][0]=max(v3[k2][0],k1);
	}
	for(int i=1;i<=n;i++){
		if(v2[i][0]>v2[i][1]||v3[i][0]>v3[i][1]){
			cout<<0<<endl;
			return;
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++)dp[i][j]=0;
		hsum[i]=lsum[i]=0;
		zz[i]=0;
	}
	dp[0][0]=3;
	hsum[0]=lsum[0]=3;
	q[lft=rgt=50000]=0;
	del(1);
	for(int i=2;i<=n;i++){
		for(int j=0;j<i-1;j++)stk[j]=(hsum[j]+lsum[j])%MOD;
		for(int j=0;j<i-1;j++)add(j,i-1,stk[j]);
		q[++rgt]=i-1;
		del(i);
	}
	ans=0;
	for(int i=0;i<=n;i++)ans=(ans+hsum[i])%MOD;
	ans%=MOD;
	ans+=MOD;
	ans%=MOD;
	cout<<ans<<endl;
	return;
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--){
		k9++;
		sol();
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3652kb

input:

4
1 0
2 0
3 0
5 2
1 3 3
4 5 1

output:

3
9
27
18

result:

ok 4 tokens

Test #2:

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

input:

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

output:

90
0
0
0
24300
0
0
0
768
0
0
972
2916
0
6480
864
0
0
0
0
0
0
0
0
6
0
0
0
0
0
96
0
6
0
0
0
0
0
0
0
108
0
0
0
2916
0
0
0
0
0
0
0
0
0
0
324
8748
0
0
0
0
0
0
4320
0
0
0
18
0
0
0
0
0
0
0
0
0
0
0
1992
0
0
450
0
162
1656
0
0
0
0
0
54
0
18
0
0
0
0
744
0
1620
324
0
0
36
36
0
0
60
6
54
0
0
0
0
0
0
0
0
243
810...

result:

ok 741 tokens

Test #3:

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

input:

332
17 5
4 9 1
4 6 1
7 17 1
5 5 1
5 6 3
13 5
10 12 3
8 13 2
1 10 3
2 9 1
9 10 1
19 5
11 13 1
9 17 2
1 7 1
4 4 2
3 9 1
15 4
8 11 2
9 14 3
10 12 2
4 5 2
12 4
3 9 2
7 8 1
1 7 3
6 7 3
16 5
4 14 3
1 5 1
2 10 1
2 12 3
6 9 3
20 4
10 17 3
4 20 3
17 19 3
8 17 1
20 5
11 11 1
9 13 1
1 5 3
17 17 3
3 18 3
17 5
1...

output:

0
0
0
2047032
0
0
0
0
0
839808
0
0
0
0
0
0
0
0
0
0
0
0
44641044
0
20412
0
0
0
0
0
0
0
6
0
0
0
0
81
0
0
0
0
0
0
0
0
0
0
0
313155072
0
0
0
0
0
0
0
0
0
5400
0
10368
0
0
0
0
14580
0
0
0
217728
40310784
0
0
218700
0
0
0
0
1620
0
0
0
0
0
108
146304
0
0
0
466560
288
0
0
0
0
0
0
0
276138
0
0
0
0
0
0
0
52488...

result:

ok 332 tokens

Test #4:

score: 0
Accepted
time: 34ms
memory: 15580kb

input:

5
1000 0
1000 5
779 779 2
543 840 3
30 477 1
10 295 3
463 741 1
1000 6
379 569 1
249 826 2
194 819 3
90 400 1
614 808 2
102 868 2
1000 8
463 981 1
680 857 3
560 623 1
209 659 1
55 957 2
244 327 1
321 888 3
37 204 3
1000 5
336 851 3
410 676 1
522 911 2
165 962 1
258 330 3

output:

56888193
0
0
0
0

result:

ok 5 tokens

Test #5:

score: 0
Accepted
time: 35ms
memory: 15468kb

input:

5
1000 9
190 765 1
212 745 3
437 798 3
682 814 3
122 289 1
44 821 1
115 448 3
400 936 2
562 639 3
1000 5
561 808 3
23 160 2
57 915 2
211 943 3
125 596 2
1000 1
398 739 2
1000 3
629 973 2
7 721 2
591 815 2
1000 10
536 708 1
217 256 2
690 913 3
418 871 2
302 325 2
334 830 2
496 573 2
396 865 1
240 837...

output:

0
0
722271060
85306976
0

result:

ok 5 tokens

Test #6:

score: 0
Accepted
time: 91ms
memory: 43032kb

input:

2
2000 1
1501 1703 2
2000 5
1230 1521 3
1022 1939 3
1241 1283 3
767 1944 2
303 1163 3

output:

841960641
0

result:

ok 2 tokens

Test #7:

score: 0
Accepted
time: 95ms
memory: 43012kb

input:

2
2000 2
640 1942 1
1473 1917 3
2000 4
490 887 1
670 1163 3
824 1434 2
1221 1746 1

output:

0
0

result:

ok 2 tokens

Test #8:

score: 0
Accepted
time: 459ms
memory: 199400kb

input:

1
5000 9
2821 3377 2
798 1535 2
3563 4161 3
2205 2946 3
1320 1594 3
278 1624 1
1243 2759 3
2882 4939 1
2639 3559 3

output:

0

result:

ok "0"

Test #9:

score: 0
Accepted
time: 383ms
memory: 199392kb

input:

1
5000 2
539 4252 1
906 3821 1

output:

101862333

result:

ok "101862333"

Test #10:

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

input:

111
34 0
30 0
18 0
35 0
3 0
43 0
13 0
28 0
57 0
75 0
31 0
4 0
92 0
1 0
53 0
85 0
74 0
43 0
59 0
72 0
79 0
40 0
70 0
36 0
86 0
56 0
53 0
66 0
50 0
100 0
60 0
74 0
50 0
51 0
92 0
49 0
50 0
78 0
95 0
4 0
59 0
44 0
92 0
84 0
7 0
75 0
99 0
56 0
54 0
13 0
27 0
33 0
22 0
80 0
14 0
79 0
29 0
39 0
21 0
97 0
...

output:

582926302
130653412
387420489
748778899
27
738321955
1594323
792294829
998064805
100094381
391960236
81
587240675
3
172815616
473062299
700031465
738321955
982583189
966670169
107644805
953271190
662963356
246336683
419186890
666021604
172815616
909419307
710104287
886041711
947749553
700031465
7101...

result:

ok 111 tokens

Test #11:

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

input:

16
350 0
453 0
485 0
361 0
498 0
149 0
433 0
435 0
279 0
240 0
166 0
152 0
393 0
159 0
219 0
222 0

output:

378029361
68761795
621961191
766744305
24977444
679213660
705815658
352340880
186665231
458529104
150230246
338768694
907169137
887128598
322586612
709838468

result:

ok 16 tokens

Test #12:

score: 0
Accepted
time: 216ms
memory: 199432kb

input:

1
5000 0

output:

22443616

result:

ok "22443616"

Test #13:

score: 0
Accepted
time: 575ms
memory: 199364kb

input:

1
5000 1000000
4736 4854 3
405 1465 3
835 4720 3
633 1954 3
2182 4257 3
1920 3098 3
302 3157 3
63 3964 3
4032 4116 3
734 1980 3
1083 4515 3
44 4768 3
20 4466 3
1160 2774 3
794 1531 3
2301 4714 3
255 4939 3
2699 2967 3
1835 2733 3
582 2071 3
430 1857 3
249 2013 3
922 4833 3
13 1973 3
3150 3812 3
2904...

output:

905890933

result:

ok "905890933"

Test #14:

score: 0
Accepted
time: 587ms
memory: 199448kb

input:

1
5000 1000000
1285 4602 3
2890 3132 3
1934 4479 3
1101 3269 3
843 3740 3
1756 3889 3
4679 4861 3
3764 3901 3
603 2768 3
4112 4680 3
470 2963 3
115 2257 3
3030 4231 3
191 4546 3
85 3688 3
65 1574 3
4025 4846 3
1968 4083 3
652 2846 3
1787 3346 3
2377 3354 3
329 2726 3
424 4954 3
805 1753 3
2038 3814 ...

output:

872513421

result:

ok "872513421"

Test #15:

score: 0
Accepted
time: 297ms
memory: 62704kb

input:

2
2500 500000
1178 2394 3
396 1815 3
1270 2004 3
385 1292 3
295 645 3
804 1281 3
740 1899 3
1922 2351 3
641 2302 3
64 1198 3
213 1246 3
1391 1525 3
211 2255 3
455 1500 3
1275 2169 3
829 2498 3
407 454 3
210 840 3
61 202 3
260 2150 3
2048 2301 3
790 971 3
2310 2469 3
144 1822 3
850 1344 3
1010 2220 3...

output:

483759098
314626501

result:

ok 2 tokens

Test #16:

score: 0
Accepted
time: 179ms
memory: 15524kb

input:

5
1000 200000
138 787 3
130 573 3
35 243 3
179 583 3
325 879 3
550 692 3
654 983 3
411 717 3
566 608 3
564 628 3
559 721 3
68 833 3
166 465 3
219 649 3
867 912 3
367 600 3
395 796 3
435 486 3
311 766 3
414 876 3
438 602 3
190 873 3
443 790 3
536 552 3
184 861 3
80 634 3
91 712 3
129 811 3
250 525 3
...

output:

580791696
25191129
596139016
823560495
689752149

result:

ok 5 tokens

Test #17:

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

input:

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

output:

1458
3
1188
108
6
24
6
18
264
1944
3
3
5292
3
12
2592
59049
18
2268
27
162
3
36
4050
3
6
36
2916
9234
6
780
144
42
3
1944
540
12
24
24
12
3
972
6
6
1296
6
9
162
9
18
6561
168
36
42
90
12150
3
12
3
3
36300
18
48
144
3240
6
324
12636
162
12
18
18
12
3
2052
108
72
2268
12
828
420
18
6
3
8748
6
648
3768...

result:

ok 900 tokens

Test #18:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

931
6 9
2 6 3
4 6 3
2 5 3
4 5 2
4 6 3
1 2 2
1 4 3
5 5 1
3 6 3
5 5
2 3 2
2 5 2
3 5 1
3 4 1
3 5 1
2 2
2 2 1
1 2 1
4 6
1 3 2
1 3 2
3 4 2
2 4 3
1 2 2
3 4 2
6 9
1 5 2
4 5 1
3 4 1
1 1 1
5 6 2
1 1 1
4 4 1
4 5 1
4 6 2
6 9
5 6 2
2 6 3
3 3 1
1 4 3
2 3 2
1 4 3
3 5 2
1 2 2
1 6 3
1 4
1 1 1
1 1 1
1 1 1
1 1 1
3 8
...

output:

42
18
3
6
36
78
3
6
9
7452
3384
7980
6
558
3
1350
6
60
4248
72
4374
240
12
3
5418
432
972
3
1944
5832
18
3
180
1458
18
24
36
6
1296
18
18
6
1026
7290
18
432
6
12
3
342
16254
6
6
1806
3
6
6
432
6
6
3
11664
729
12
18
6
72
12
54
72
21060
3
17334
12
504
24
6
1512
3
18
18
3
54450
3096
12
54
864
3
6
3
3
3...

result:

ok 931 tokens

Test #19:

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

input:

167
24 1
8 16 3
18 7
2 15 3
1 6 3
6 15 3
7 16 3
13 17 2
1 4 3
2 10 2
36 8
19 26 3
16 22 3
2 4 3
14 23 3
29 34 3
9 30 3
8 17 3
15 26 3
23 10
1 23 3
11 19 2
1 7 2
2 13 3
1 6 2
10 23 3
11 14 2
5 6 1
11 12 1
11 17 2
15 9
5 15 3
6 9 2
5 12 2
3 6 2
4 8 2
6 15 3
8 13 3
5 10 2
4 7 2
38 10
1 5 3
4 28 3
15 27...

output:

432660230
2245104
627174419
171391104
191484
881689777
6732
708133104
452584625
452272890
63452160
50544
563306692
456409929
577806546
164497392
926733632
749173271
9920232
630862855
87864912
42751818
397426605
238587552
286978140
148803480
741052156
953868636
693852914
35770332
348768
534086631
251...

result:

ok 167 tokens

Test #20:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

171
31 3
22 30 3
6 8 2
2 13 3
18 7
10 17 3
2 18 3
8 14 3
7 13 3
5 5 1
2 10 3
3 13 3
18 5
8 11 3
4 15 3
16 18 2
5 18 3
9 16 3
34 1
8 26 3
27 2
5 6 1
15 17 2
25 8
11 18 3
20 20 1
8 15 3
6 22 3
12 18 3
2 12 3
3 10 2
2 10 2
18 2
9 10 2
2 3 1
29 10
2 5 3
6 16 3
8 24 3
5 6 2
7 25 3
16 26 3
26 26 1
8 13 3
...

output:

668830469
255926304
107232984
746871358
577207028
35180417
86093442
222527232
721842180
567840937
736320076
343448979
768882859
621257551
125653397
86388920
215236761
532288892
868032
932169620
568620
760476876
86891305
793936979
947742183
777097753
880104893
594433882
638041958
3969000
144902522
86...

result:

ok 171 tokens

Test #21:

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

input:

32
148 161
67 123 3
73 121 3
75 147 3
11 132 3
4 19 3
76 112 3
27 38 3
74 139 3
43 117 3
8 85 3
54 71 3
6 121 3
47 107 3
126 137 3
6 52 3
76 147 3
22 144 3
45 62 3
23 75 3
110 148 3
112 143 3
24 128 3
93 95 2
118 125 3
13 24 3
56 84 3
42 58 3
8 32 3
30 138 3
21 115 3
94 115 3
74 141 3
38 138 3
42 13...

output:

13045160
791524212
919602433
185984480
284687373
315018328
647668718
667435283
220748425
26419791
350330436
111886901
724898498
824707885
524867436
699924001
904496950
607447270
712709586
810776827
928352606
417947063
519074740
672603637
329069921
859239592
876468549
820925057
388955240
165696894
58...

result:

ok 32 tokens

Test #22:

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

input:

33
194 106
58 165 3
108 110 2
76 93 3
40 151 3
75 134 3
51 169 3
4 112 3
129 162 3
30 143 3
116 140 3
76 165 3
169 178 3
32 45 3
86 100 3
164 182 3
107 139 3
157 167 3
119 189 3
77 135 3
27 95 3
113 182 3
119 126 3
58 89 3
63 135 3
25 47 3
53 113 3
59 64 3
116 117 2
137 150 3
16 151 3
37 176 3
151 1...

output:

421555226
30549649
564415231
232134499
631155763
831654406
817121388
914358044
571784267
930030731
215742475
198373421
281810818
310038824
534037843
210943058
628089409
333961861
405141696
453666588
35217959
408347203
434576565
538356731
64580789
295873970
819437496
45903387
164573238
148326025
8202...

result:

ok 33 tokens

Test #23:

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

input:

14
464 173
368 432 3
270 310 3
243 370 3
174 356 3
180 320 3
224 308 3
208 362 3
83 410 3
46 242 3
50 118 3
88 398 3
45 252 3
378 456 3
119 437 3
375 380 2
47 371 3
94 403 3
49 279 3
141 222 3
95 129 3
211 341 3
128 182 3
30 362 3
99 170 3
71 347 3
375 410 3
55 141 3
87 189 3
61 427 3
40 75 3
253 36...

output:

453237503
25416587
641731796
360432117
478970935
824952511
225391939
605219631
330907283
830674309
41958175
65368401
517400374
799272766

result:

ok 14 tokens

Test #24:

score: 0
Accepted
time: 9ms
memory: 7544kb

input:

15
365 129
175 283 3
126 313 3
73 285 3
246 323 3
122 195 3
108 280 3
114 181 3
73 361 3
160 331 3
225 251 3
132 317 3
98 353 3
75 115 3
162 349 3
115 325 3
189 272 3
118 276 3
32 160 3
61 159 3
168 288 3
150 205 3
257 298 3
50 314 3
63 172 3
14 248 3
6 84 3
57 364 3
65 256 3
49 177 3
244 338 3
107 ...

output:

99377382
9189569
575369230
284536280
716140421
178937920
835042295
749498990
199245931
463318804
305246319
85387991
563488532
933996923
769555855

result:

ok 15 tokens

Test #25:

score: 0
Accepted
time: 53ms
memory: 15580kb

input:

5
1000 8985
258 755 3
380 863 3
461 595 3
27 732 3
813 873 3
151 381 3
190 446 3
70 390 3
509 844 3
235 339 3
216 503 3
788 929 3
255 551 3
795 878 3
287 459 3
590 630 3
152 368 3
208 823 3
352 894 3
127 405 3
250 664 3
23 452 3
833 894 3
56 246 3
116 599 3
871 975 3
37 160 3
453 583 3
440 657 3
536...

output:

505832166
103520863
175172607
414025257
278523209

result:

ok 5 tokens

Test #26:

score: 0
Accepted
time: 79ms
memory: 15456kb

input:

5
1000 60351
123 559 3
199 513 3
949 984 3
149 629 3
328 627 3
649 986 3
11 590 3
71 327 3
177 753 3
238 851 3
163 792 3
163 658 3
635 877 3
326 723 3
50 507 3
572 956 3
658 684 3
36 915 3
410 558 3
416 953 3
171 508 3
287 525 3
47 849 3
157 462 3
833 980 3
434 817 3
709 903 3
230 888 3
65 273 3
623...

output:

396010750
694382863
545030920
734433178
621494141

result:

ok 5 tokens

Test #27:

score: 0
Accepted
time: 86ms
memory: 43028kb

input:

2
2000 2122
1390 1424 3
1139 1349 3
831 1037 3
1868 1903 3
83 178 3
540 1029 3
539 1321 3
875 1021 3
1298 1895 3
1344 1749 3
348 1490 3
1595 1771 3
1051 1241 3
609 1376 3
254 1110 3
222 1906 3
708 1548 3
303 556 3
632 1962 3
515 1915 3
369 1992 3
592 1215 3
456 1016 3
1359 1517 3
1192 1246 3
1190 16...

output:

124443009
53366353

result:

ok 2 tokens

Test #28:

score: 0
Accepted
time: 124ms
memory: 43004kb

input:

2
2000 99850
1088 1566 3
1286 1594 3
302 1698 3
158 1041 3
1916 1937 3
1637 1961 3
226 913 3
153 1112 3
1081 1393 3
234 1851 3
48 1461 3
1680 1792 3
181 1189 3
275 504 3
1070 1980 3
60 1106 3
1132 1744 3
900 1485 3
33 1650 3
257 427 3
1676 1848 3
1012 1093 3
1663 1699 3
37 712 3
226 1586 3
807 1373 ...

output:

72462725
636071590

result:

ok 2 tokens

Test #29:

score: 0
Accepted
time: 243ms
memory: 199412kb

input:

1
5000 10
1843 3270 3
1387 1926 3
929 2817 3
809 4781 3
524 2042 3
2659 2859 3
4279 4647 3
91 305 3
2922 3089 3
800 3166 3

output:

914610603

result:

ok "914610603"

Test #30:

score: 0
Accepted
time: 332ms
memory: 199368kb

input:

1
5000 100
2163 4279 3
3098 3995 3
1001 1597 3
4177 4544 3
1940 3017 3
2099 4851 3
139 4259 3
1626 1639 3
2130 3742 3
1416 4154 3
2055 2849 3
2000 3548 3
1635 2194 3
1197 4900 3
3361 4077 3
1011 1888 3
2228 2813 3
807 3702 3
651 3191 3
77 3723 3
1663 1732 3
699 2917 3
825 1454 3
143 1464 3
634 1452 ...

output:

682663814

result:

ok "682663814"

Test #31:

score: 0
Accepted
time: 424ms
memory: 199348kb

input:

1
5000 1000
262 2424 3
437 3916 3
285 1255 3
760 3530 3
2995 3991 3
2606 2889 3
2164 3199 3
1164 2726 3
560 4892 3
381 2332 3
619 2230 3
258 931 3
1371 3100 3
917 1234 3
795 1143 3
113 2582 3
2085 3080 3
543 3590 3
1375 3167 3
3969 4505 3
1557 2339 3
469 4743 3
834 4725 3
2197 3073 3
435 4390 3
2044...

output:

831070180

result:

ok "831070180"

Test #32:

score: 0
Accepted
time: 406ms
memory: 199432kb

input:

1
5000 10000
2705 3313 3
1976 5000 3
61 2100 3
1217 2662 3
2778 3429 3
241 4888 3
4219 4845 3
2126 4158 3
1621 4512 3
828 2997 3
697 4273 3
1169 2716 3
110 176 3
768 2886 3
1905 3124 3
378 4927 3
4300 4991 3
934 3648 3
2698 3653 3
1584 4244 3
973 2754 3
2899 3036 3
113 4337 3
2365 4313 3
3069 3086 3...

output:

26748419

result:

ok "26748419"

Test #33:

score: 0
Accepted
time: 458ms
memory: 199368kb

input:

1
5000 100000
3346 4758 3
914 3487 3
275 1070 3
881 1033 3
3139 3327 3
1284 3977 3
908 3270 3
2996 3826 3
2867 3823 3
491 2512 3
3172 4567 3
4049 4197 3
1187 4888 3
391 2847 3
4698 4834 3
2033 4436 3
3420 3705 3
1225 4174 3
468 501 3
2873 4545 3
1084 1408 3
310 1835 3
1452 3910 3
799 3275 3
4031 481...

output:

87641236

result:

ok "87641236"