QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#290594#3270. 魔塔 OLMoRanSky100 ✓1134ms26380kbC++234.1kb2023-12-25 06:00:302023-12-25 06:00:31

Judging History

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

  • [2023-12-25 06:00:31]
  • 评测
  • 测评结果:100
  • 用时:1134ms
  • 内存:26380kb
  • [2023-12-25 06:00:30]
  • 提交

answer

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 50005, M = 150005, B = 14;

int q, n, ty[N], id[3], ps[N], tot, p1[N], p2[N], Lg[1 << B], O = 10000;

char op[5];

struct E{
	int x, y, z, a, b;
} e[N];

bool st[N];

struct Node{
	LL s, mn;
};

struct W{
	int C[3];
	Node W;
};

Node inline operator + (const Node &a, const Node &b) {
	return (Node) { a.s + b.s, min(a.mn, a.s + b.mn) };
}


struct Tas{
	int OP[M], D[M][3], ID[M];
	W a[N];
	int n, m, p[N], ar[3][N], idt;
	Node ans[N];
	vector<PII> tr[N];
	void inline insS(int x) {
		tr[(x - 1) / B + 1].pb(mp(m + 1, x));
	}
	void inline insQ(int id, int x, int y, int z) {
		++m;
		ID[m] = id;
		D[m][0] = x, D[m][1] = y, D[m][2] = z;
	}
	void inline insE(int x, int y, int z, Node o) {
		++n;
		a[n].C[0] = x;
		a[n].C[1] = y;
		a[n].C[2] = z;
		a[n].W = o;
	}
	Node val[1 << B];
	int st[M], z[3][N];
	int o;
	bool ct(int x, int y) {
		return a[x].C[o] < a[y].C[o];
	}
	int b;
	void inline work(int l, int r) {
		int t = r - l + 1;
		for (int i = 1; i < (1 << t); i++) {
			val[i] = a[l + Lg[i & -i]].W + val[i ^ (i & -i)];
		}
		int now = 0;
		for (int i = 1; i <= m; i++) st[i] = (1 << t) - 1;
		for (int i = l; i <= r; i++) p[i] = i;
		for (int t = 0; t < 3; t++) {
			o = t;
			sort(p + l, p + 1 + r, [&](int x,int y){return a[x].C[o] < a[y].C[o];});
			now = 0;
			for (int i = 1; i < a[p[l]].C[t]; i++)
				z[t][i] = 0;
			for (int i = l; i <= r; i++) {
				now ^= 1 << (p[i] - l);
				int rt = i == r ? O : a[p[i + 1]].C[t] - 1;
				for (int j = a[p[i]].C[t]; j <= rt; j++)
					z[t][j] = now;
			}
		}
		now = 0;
		int len = tr[b].size();
		for (int i = 0; i < len; i++) {
			now ^= 1 << (tr[b][i].se - l);
			if (i == len - 1 || tr[b][i].fi != tr[b][i + 1].fi) {
				int r = i == len - 1 ? m : tr[b][i + 1].fi - 1;
				for (int j = tr[b][i].fi; j <= r; j++) {
					ans[j] = ans[j] + val[now & z[0][D[j][0]] & z[1][D[j][1]] & z[2][D[j][2]]];
				}
			}
		}
	}
	void inline work() {
		for (int i = 1; i <= n; i += B) {
			int r = min(n, i + B - 1);
			++b;
			work(i, r);
		}
	}
} t1, t2;

bool inline cmp1(int x, int y) {
	return e[x].a < e[y].a;
}

bool inline cmp2(int x, int y) {
	return e[x].b > e[y].b;
}

int G[M], L[M], D[M], OP[M];

int main() {
	for (int i = 0; i < B; i++) Lg[1 << i] = i;
	read(q);
	for (int i = 1; i <= q; i++) {
		scanf("%s", op);
		if (op[0] == '+') {
			int x, y, z, a, b;
			read(x), read(y), read(z), read(a), read(b);
			e[++n] = (E) { x, y, z, a, b };
			G[i] = n;
		} else if (op[0] == '-') {
			int k; read(k);
			G[i] = k;
		} else {
			OP[i] = 1;
			int g, l, d; read(g), read(l), read(d);
			G[i] = g, L[i] = l, D[i] = d;
		}
	}
	for (int i = 1; i <= n; i++) p1[i] = p2[i] = i;
	sort(p1 + 1, p1 + 1 + n, cmp1);
	sort(p2 + 1, p2 + 1 + n, cmp2);
	for (int i = 1; i <= n; i++) {
		int u = p1[i];
		if (e[u].a <= e[u].b) {
			ps[u] = ++id[1];
			t1.insE(e[u].x, e[u].y, e[u].z, (Node){ -e[u].a + e[u].b, -e[u].a});
			ty[u] = 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		int u = p2[i];
		if (e[u].a > e[u].b) {
			ps[u] = ++id[2];
			t2.insE(e[u].x, e[u].y, e[u].z, (Node){ -e[u].a + e[u].b, -e[u].a});
			ty[u] = 2;
		}
	}
	for (int i = 1; i <= q; i++) {
		if (!OP[i]) {
			if (ty[G[i]] == 1) t1.insS(ps[G[i]]);
			else t2.insS(ps[G[i]]);
		} else {
			int g = G[i], l = L[i], d = D[i];
			++tot;
			t1.insQ(tot, g, l, d);
			t2.insQ(tot, g, l, d);
		}
	}
	t1.work(), t2.work();
	for (int i = 1; i <= tot; i++) {
		Node u = t1.ans[i] + t2.ans[i];
		printf("%lld\n", -u.mn);
	}
    return 0;
}


详细

Subtask #1:

score: 3
Accepted

Test #1:

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

input:

10
+ 2 1 1 3 4
+ 1 2 2 2 5
? 2 2 2
+ 1 1 1 8 2
? 2 2 1
? 1 2 2
- 1
? 2 2 2
- 3
? 1 2 2

output:

2
7
5
5
2

result:

ok 5 lines

Test #2:

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

input:

24
+ 1753 1095 4823 848018166 5601858
+ 3635 2923 7293 78801729 4982097
+ 4314 6396 5125 589512425 8363663
? 8152 8403 6056
+ 9016 7943 8050 764333567 3409718
? 3516 8598 7385
? 1126 7574 1443
+ 2684 1515 2348 83534456 3012204
- 5
? 1861 8978 2163
- 4
? 480 2246 9251
- 1
+ 3844 6148 4596 110822346 7...

output:

1429166928
848018166
0
0
0
0
0
0

result:

ok 8 lines

Test #3:

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

input:

24
+ 9833 6751 5339 125176046 14445
+ 1422 2896 2855 729112474 32204
+ 636 3368 6257 631353523 97285
+ 7661 7136 8410 801391911 74940
? 7519 1330 3067
? 9524 4467 711
? 2291 8608 9213
- 1
? 1174 1586 7861
? 2265 4657 349
? 8213 4439 7824
+ 9135 101 6409 977821442 34327
+ 1115 2298 9752 392083250 697...

output:

0
0
1360368712
0
0
1360368712
729112474
729112474

result:

ok 8 lines

Test #4:

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

input:

24
+ 5489 9970 1398 56343180 451
+ 1396 1562 433 123478310 271
- 2
+ 7608 4501 7224 982256325 947
- 3
? 9813 5754 2918
? 2389 7502 4690
+ 5393 498 3406 73387341 297
? 621 6378 5221
? 3593 3767 6323
- 1
+ 3286 7926 6941 820762494 364
- 5
+ 8217 6480 9506 484820290 71
- 6
+ 9300 262 4419 859278667 105...

output:

0
0
0
0
0
0
0
0

result:

ok 8 lines

Test #5:

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

input:

8
? 1117 6081 8661
? 5702 6655 5962
? 4712 8281 9732
? 4472 3953 2253
? 8402 8576 2723
? 8258 6776 1630
? 9363 4534 9896
? 8271 8778 1846

output:

0
0
0
0
0
0
0
0

result:

ok 8 lines

Test #6:

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

input:

24
+ 310 6758 7068 581664379 614379561
? 431 4963 9146
+ 8040 7145 2374 921183974 119186212
? 739 2475 4540
+ 7023 2014 2972 87001226 131388922
+ 332 1474 3058 965714110 106555937
- 1
? 6232 3770 731
? 3571 5680 4059
+ 6128 4706 1280 517406107 709876522
? 7499 5319 7619
? 8343 4010 2781
+ 2990 2854 ...

output:

0
0
0
965714110
728855999
0
191994852
191994852

result:

ok 8 lines

Test #7:

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

input:

24
? 7531 9176 7945
+ 6869 6976 9568 811496150 65260266
+ 6002 7147 3653 399332739 802592034
+ 1589 1206 9875 491845336 674971274
+ 2606 7949 8709 732507238 685138894
- 4
- 3
+ 7773 2691 4846 806580794 444791436
? 8302 1260 612
+ 9474 585 6602 228111503 673775897
+ 7377 2531 1730 989204815 313215502...

output:

0
0
0
0
0
0
0
0

result:

ok 8 lines

Test #8:

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

input:

24
+ 6076 6882 697 357720969 18505713
+ 8522 7101 7498 273203817 247602668
+ 5282 5228 6668 389453604 672327934
? 6379 8137 1715
? 7691 1160 2306
+ 2065 3609 2107 39462790 995011849
- 2
+ 7821 3053 4992 54012550 598488583
? 2742 7408 4111
+ 8142 2626 2703 378261715 799364458
+ 8988 6063 8298 8459843...

output:

357720969
0
39462790
0
0
0
0
0

result:

ok 8 lines

Test #9:

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

input:

24
+ 4703 1944 1160 450781972 720568789
+ 3502 6991 8127 106832475 971539963
? 3141 943 3234
+ 5361 8172 8148 172500308 209720541
- 3
- 1
+ 4124 2386 6673 396124268 408795532
+ 7267 8100 7795 710193258 706757641
? 3147 654 9372
+ 7795 2301 1587 223112271 672239899
? 4553 738 5182
+ 6188 7219 243 764...

output:

0
0
0
0
0
0
0
0

result:

ok 8 lines

Test #10:

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

input:

24
+ 1015 3099 4819 69198894 934987604
+ 1971 6075 3089 18416465 126949453
+ 3346 4984 4780 756144 637251010
+ 9173 1405 1768 90360802 606947317
+ 1452 1393 6947 86736593 700812438
+ 7794 9412 1997 52466993 263586896
- 5
+ 6442 6634 8262 33830753 203825632
? 5518 522 7828
- 1
- 3
+ 3365 8793 7708 64...

output:

0
0
0
0
0
0
0
0

result:

ok 8 lines

Test #11:

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

input:

24
+ 9703 133 3965 55149 848473280
? 794 7392 2211
? 6854 1133 7922
+ 5774 6768 6550 19909 92266756
- 2
? 4784 2895 2924
+ 2589 9679 8865 93993 586178413
+ 6266 516 8968 99691 77932883
? 5982 5547 905
+ 7947 3208 3227 44903 268728227
- 5
- 4
+ 6508 3419 6547 26144 770044013
? 3120 2629 5910
+ 8616 2...

output:

0
0
0
0
0
0
0
0

result:

ok 8 lines

Test #12:

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

input:

24
+ 3428 3207 272 398860932 94104753
? 7644 5501 6242
? 4375 4880 3925
? 1803 4173 8176
? 6042 1710 2170
+ 3748 5518 3602 909430193 42284174
+ 3649 9013 9199 375710242 7718045
- 3
? 919 5751 4803
+ 3223 324 8116 531239473 10475148
? 1915 3129 9903
+ 7144 6800 8556 652921806 11521155
- 1
- 4
+ 4427 ...

output:

398860932
398860932
0
0
0
0
432397460
0

result:

ok 8 lines

Subtask #2:

score: 7
Accepted

Dependency #1:

100%
Accepted

Test #13:

score: 7
Accepted
time: 19ms
memory: 20756kb

input:

15000
+ 9754 4951 2299 36950620 330476254
? 7852 3754 6437
+ 7960 5847 3889 877365182 511620385
+ 2042 1318 3674 509235230 295832114
+ 8026 1900 3586 787277573 238947685
? 3297 71 4102
? 7652 9321 3721
? 1782 8456 2128
? 3892 8535 3934
+ 4911 3952 9686 951709847 5471156
+ 567 5092 9346 132609563 645...

output:

0
0
509235230
0
509235230
0
0
799337462
0
0
0
575363546
0
955299529
799337462
0
0
1724967630
320029391
590850186
1250598046
0
548236941
509235230
548236941
389915580
509235230
0
578425355
799337462
1197972240
0
0
35119488
837528941
758929477
891443369
548236941
0
1242763152
0
35119488
0
0
0
0
351194...

result:

ok 5000 lines

Test #14:

score: 0
Accepted
time: 27ms
memory: 22656kb

input:

15000
+ 9000 6045 9181 863134447 327523157
+ 5800 3917 4897 494849846 170888604
+ 8224 524 7309 567221629 163056241
? 2839 4181 2426
? 1731 3056 6432
+ 8778 8718 3130 146110843 137080516
+ 4985 3689 8556 456546147 7602401
+ 356 9954 3979 273061519 454609666
+ 1209 9046 4448 642768233 777950592
+ 879...

output:

0
0
0
144925021
0
0
846135812
0
0
0
1426212455
1659355410
827991846
846135812
1194975799
0
846135812
377185177
0
248809656
2138119062
438946756
0
438946756
2724060363
748592853
0
873547760
846135812
0
383144069
227838083
39166976
39166976
39166976
846135812
39166976
39166976
39166976
3947224442
3916...

result:

ok 5000 lines

Test #15:

score: 0
Accepted
time: 19ms
memory: 22596kb

input:

15000
+ 951 7138 255 320722052 324570060
+ 2596 7803 3430 410802879 748644857
? 3555 6250 6021
? 3881 2359 5828
? 2110 933 7043
+ 4862 2175 1664 481128464 24445604
? 1280 3044 69
+ 368 299 6465 110630763 605821477
+ 1298 1572 1823 6340608 435831189
+ 8497 471 8990 862173030 294426772
? 2582 3988 118...

output:

0
0
0
0
0
6340608
6340608
184769081
0
6340608
6340608
110630763
6340608
6340608
0
184769081
0
110630763
144559506
6340608
0
0
184769081
0
6340608
6340608
6340608
284186499
209374819
6340608
6340608
166088998
600045165
0
24708843
6340608
6340608
6340608
110630763
600045165
6340608
0
6340608
6340608
6...

result:

ok 5000 lines

Test #16:

score: 0
Accepted
time: 26ms
memory: 22580kb

input:

15000
? 1330 3972 8167
+ 7771 2045 28 71596349 316831431
+ 4392 5643 8439 793300118 365317022
? 1145 1085 1131
? 1981 4834 3010
? 7898 2215 2137
+ 9452 8525 6012 308068582 222805994
+ 3109 1021 3834 149338880 460129515
+ 8252 8596 2476 25387218 893568152
+ 9457 8518 1637 365077612 577489093
+ 7750 4...

output:

0
0
0
71596349
0
149338880
0
0
71596349
149338880
482509483
0
149338880
0
339204739
0
0
149338880
646121546
0
339204739
0
347036011
0
0
840777389
0
818079693
25387218
0
8400682
0
28267956
586256202
940165346
0
8400682
5137674
940165346
0
0
1146605530
623425462
1009743383
8400682
0
0
0
8400682
635897...

result:

ok 5000 lines

Test #17:

score: 0
Accepted
time: 26ms
memory: 18712kb

input:

15000
? 8212 7747 6199
? 5369 4852 6221
+ 857 4971 2870 21781664 537676236
? 9139 6445 3549
? 8576 2601 6708
+ 4132 7656 9581 659855253 194286236
? 3171 5622 517
? 3171 327 2791
+ 5787 5851 4846 918160613 261675926
+ 1379 2503 9812 686149995 413030048
+ 320 3121 1973 208594175 204418683
+ 9169 5837 ...

output:

0
0
21781664
0
0
0
0
0
417771032
0
933665604
208594175
249449409
21781664
21781664
417771032
0
0
986604907
29341218
21781664
29341218
173452390
173452390
29341218
0
310828376
302388712
310828376
0
0
698493757
173452390
7884628
0
85153293
21781664
0
0
643737804
0
10510955
7884628
21781664
1387723437
...

result:

ok 5000 lines

Test #18:

score: 0
Accepted
time: 22ms
memory: 18892kb

input:

15000
+ 837 3441 1582 5253755 930660276
? 8689 9131 528
+ 4211 2422 5160 6252539 907522408
? 5609 9790 4958
+ 3432 9848 2969 4896645 940041091
+ 3206 796 2996 4324022 502262890
+ 5174 3152 4568 113382 730527877
+ 980 3333 9883 3057033 196077695
+ 4799 5142 3509 3458598 100286630
+ 9905 3615 8329 927...

output:

0
5253755
3458598
5253755
5253755
5253755
9436006
4324022
113382
113382
4324022
4324022
0
0
867679
0
0
782618
867679
867679
0
0
5253755
0
867679
0
782618
0
0
867679
113382
113382
0
867679
0
867679
0
0
867679
782618
0
0
0
0
0
867679
867679
113382
782618
0
700552
535909
0
535909
535909
1670398
535909
...

result:

ok 5000 lines

Test #19:

score: 0
Accepted
time: 25ms
memory: 18636kb

input:

15000
? 3626 6634 706
? 582 4658 8319
+ 8038 8232 6351 148817232 19413256
+ 3461 40 3308 437404415 36165359
+ 4151 5967 4070 30914737 15176710
? 1288 5080 6184
+ 4930 9177 4330 947817077 4805014
? 5408 4013 1507
+ 1577 348 6484 542555954 13288929
+ 5453 364 6644 751430050 669281
? 5356 1904 8389
+ 7...

output:

0
0
0
0
943795010
1681936131
270965968
1382835375
0
3579152160
2639972120
632435278
3039344651
270965968
0
270965968
437404415
0
270965968
0
9127712031
2340849315
7463345443
0
1359397476
0
1377000336
0
3316860695
437404415
9298965753
380650058
1538402434
380650058
417208885
4307614967
400461565
0
0
...

result:

ok 5000 lines

Test #20:

score: 0
Accepted
time: 26ms
memory: 22596kb

input:

15000
? 3611 820 322
+ 68 6093 7344 309660603 8512708
+ 9882 7331 2103 909793528 3687386
+ 1138 4890 983 723391503 1141995
+ 4152 9237 9559 368251712 1852709
+ 1125 9752 5938 889181325 3511910
+ 3283 9654 5264 798148638 5602588
+ 3969 5422 5395 231270203 718652
+ 844 9893 7504 648724319 7248904
+ 64...

output:

0
0
0
723391503
723391503
1842658494
3508915764
90640885
2547470891
0
234293253
2126743406
0
1886611066
1362525704
90640885
0
0
234293253
6846238386
0
5602549623
2436552350
1238971762
2141877364
920903399
4563307221
0
0
0
723391503
0
10337046004
652693183
0
2094945541
723391503
19414268394
652693183...

result:

ok 5000 lines

Test #21:

score: 0
Accepted
time: 30ms
memory: 22764kb

input:

15000
+ 2801 8433 1829 827936405 969585
? 3554 6367 5498
+ 2376 6776 7720 574207248 923476
+ 6613 3146 9378 418383056 692192
? 5159 1876 4183
? 8151 2128 7976
+ 5623 5911 6955 870974472 262457
+ 7705 3889 1572 267612426 193840
+ 5878 8297 1889 949419857 909460
? 2892 6894 9481
+ 9002 6208 2127 17602...

output:

0
0
0
574207248
1447046366
220786949
220786949
198485575
0
0
220786949
0
4729943861
1058959264
6235959933
0
4713794925
0
0
2808741354
8162816820
14909424
0
615261353
497270752
1066222454
6951160136
2520242767
937344669
101280125
2250020267
0
11483417654
1946958292
517978806
14909424
14909424
3799993...

result:

ok 5000 lines

Test #22:

score: 0
Accepted
time: 18ms
memory: 18652kb

input:

15000
? 1822 8820 1908
? 6083 1623 4227
+ 2418 2824 8807 17003027 76795
+ 8008 4258 9437 554693365 68917
? 2489 3921 7965
+ 3031 2477 9191 233409376 44619
+ 275 7141 8883 632058327 24232
? 2823 344 8326
? 4155 616 839
+ 4987 8144 4847 428926401 72189
+ 1182 1452 4110 318600919 38488
? 7018 1554 9239...

output:

0
0
0
0
0
318600919
318600919
318600919
318600919
822156885
1752483691
301111585
0
301111585
830297218
301111585
830297218
2204007159
0
318600919
338944729
422177019
810476550
948847527
0
0
0
931541984
2883343968
2060522423
5573300097
2636499601
810476550
318600919
3775501120
0
5139311198
2342378136...

result:

ok 5000 lines

Test #23:

score: 0
Accepted
time: 26ms
memory: 22548kb

input:

15000
? 4398 952 1402
+ 6182 1283 9449 125619308 3324
+ 5052 3754 4403 940063798 7205
? 5829 8922 1931
? 3773 9074 6359
+ 5199 3920 7495 700019470 6744
+ 5061 4344 6013 240536850 6853
+ 822 2757 5213 726945179 9781
+ 2472 2802 3895 668906250 3499
+ 7575 213 5230 996820178 794
? 2508 2979 6516
+ 7428...

output:

0
0
0
1395841648
0
1395841648
0
0
5247832105
249492314
6975588404
9526409743
1269626113
0
0
0
3312824127
0
0
1388900157
1130300143
0
6478380651
0
675045491
0
0
971474622
0
15013028304
7606104219
724850564
1858905499
49811071
249492314
2109763404
21604570710
3196438136
2036028508
1595679425
231376802...

result:

ok 5000 lines

Subtask #3:

score: 10
Accepted

Test #24:

score: 10
Accepted
time: 782ms
memory: 26120kb

input:

150000
+ 588 392 1 640173034 0
? 7190 2026 1
? 8338 9467 1
+ 332 5522 1 648776911 0
? 650 9239 1
? 6609 1361 1
+ 6028 8919 1 315490561 0
+ 6129 3818 1 716541323 0
+ 2679 2249 1 94302018 0
? 4777 8851 1
+ 1382 186 1 295931805 0
+ 3956 7752 1 275694182 0
+ 6412 2498 1 363908456 0
+ 8317 3132 1 2800724...

output:

640173034
640173034
1288949945
640173034
1383251963
648776911
936263387
6225405294
1584881750
1100294298
6171086456
5704673070
4575914076
3155191047
8023603142
2527253525
7167405476
0
10195623880
0
1402795465
4984468602
11654616273
1473610256
2027968013
4367888241
2304906071
2304906071
12018094056
2...

result:

ok 50000 lines

Test #25:

score: 0
Accepted
time: 792ms
memory: 24368kb

input:

150000
+ 1787 8939 1 339346728 0
+ 3158 5092 1 855389002 0
+ 7832 1673 1 721154315 0
+ 1707 6586 1 559360588 0
? 6285 2437 1
+ 1490 7002 1 739345914 0
? 2815 2609 1
+ 8527 8829 1 367297793 0
+ 923 6751 1 126310301 0
+ 2810 6129 1 875334002 0
+ 7149 9872 1 658890299 0
+ 3495 467 1 349126714 0
+ 356 2...

output:

0
0
2915271787
4145341563
989601756
0
989601756
989601756
8854347677
7055669482
5291303583
3870297099
1187229746
7148740547
466075431
2404621423
7775443142
7682961442
2305192137
349126714
3903312117
14509564923
0
9584525312
5959691046
16191460507
6321152285
15631009768
4090015118
8330922702
14987834...

result:

ok 50000 lines

Test #26:

score: 0
Accepted
time: 765ms
memory: 23628kb

input:

150000
? 9819 7010 1
+ 1517 9319 1 761082020 0
? 6420 6850 1
+ 9950 5950 1 915549489 0
+ 7039 2434 1 92974186 0
+ 2913 7849 1 984734480 0
+ 4517 8118 1 250711080 0
+ 7909 3583 1 184025459 0
+ 9524 1430 1 864047763 0
? 7547 9033 1
? 5504 5205 1
? 8491 3037 1
? 1043 3152 1
+ 9676 3886 1 426915433 0
+ ...

output:

0
0
1328419746
0
92974186
0
0
1323840030
199448068
0
0
0
1787413459
2330784601
2943820662
964261394
2925703990
1905971976
0
18077736464
7978811233
964261394
18814278526
18098823816
5066562470
8962935888
2311793337
1347531943
1347531943
2919782139
0
0
10193662595
10789276500
2542720149
3455776134
120...

result:

ok 50000 lines

Test #27:

score: 0
Accepted
time: 761ms
memory: 23836kb

input:

150000
+ 930 118 1 979534399 0
? 484 60 1
? 365 143 1
? 19 252 1
+ 775 105 1 354040505 0
? 426 541 1
? 781 435 1
+ 314 306 1 4398445 0
+ 499 855 1 429484536 0
? 440 138 1
+ 855 955 1 687386644 0
+ 10 197 1 910103250 0
+ 217 375 1 770690507 0
? 401 111 1
+ 787 484 1 914331856 0
+ 907 872 1 789691385 ...

output:

0
0
0
0
354040505
0
0
354040505
1560780741
1952278514
3995739827
1084865603
4343100163
3107365561
2631450423
2627051978
1842473665
1084865603
1842473665
12282151973
0
7739054592
8715250511
5807771088
7236124275
0
0
8006814782
568585700
3086025393
2517439693
0
7314249953
2517439693
6965559181
7012239...

result:

ok 50000 lines

Test #28:

score: 0
Accepted
time: 773ms
memory: 23832kb

input:

150000
+ 50 37 1 708972468 0
+ 18 62 1 186412810 0
? 42 92 1
+ 70 63 1 499167214 0
+ 87 37 1 9753881 0
+ 25 10 1 962187904 0
? 89 74 1
+ 93 17 1 414130698 0
+ 97 87 1 103340756 0
+ 79 5 1 737466371 0
+ 70 98 1 383081284 0
+ 30 18 1 950133777 0
+ 78 23 1 430459053 0
? 44 52 1
+ 27 70 1 866104461 0
+ ...

output:

186412810
2366494277
1912321681
1699654275
962187904
3494377803
962187904
3143862341
8986387511
0
737466371
3080247105
0
7624657274
214083964
4024194299
2437128825
5998424714
10777980738
10308326178
6943671240
1341655112
1746138247
3046563132
6436272368
13163376501
214083964
5840292537
1000922619
52...

result:

ok 50000 lines

Test #29:

score: 0
Accepted
time: 691ms
memory: 23728kb

input:

150000
? 7 7 1
+ 4 1 1 684861229 0
? 8 4 1
+ 8 4 1 394234759 0
? 10 7 1
+ 8 10 1 174933586 0
+ 1 8 1 155093080 0
+ 3 5 1 360569664 0
+ 8 1 1 302476341 0
? 5 4 1
+ 3 1 1 309477964 0
+ 6 5 1 3345418 0
+ 1 9 1 31128204 0
+ 7 10 1 261898040 0
+ 6 10 1 20868263 0
+ 4 1 1 413664169 0
+ 3 8 1 660018338 0
+...

output:

0
684861229
1079095988
684861229
502073680
0
1945242559
502073680
309477964
0
0
4584156270
4770082565
7294103543
9629605008
12410412318
16531903872
10808215457
15636388917
2380411498
7702220303
10940353825
11254320459
10890764062
20674654718
4460547161
7598640300
25980420587
25606338059
1636053588
3...

result:

ok 50000 lines

Test #30:

score: 0
Accepted
time: 505ms
memory: 22228kb

input:

101000
+ 7599 908 1 339097838 0
+ 9787 306 1 529271711 0
+ 9497 9109 1 443251017 0
+ 4989 876 1 24346088 0
+ 4439 9648 1 148703162 0
+ 7017 3441 1 29320835 0
+ 8321 6853 1 38406269 0
+ 9000 5957 1 984032881 0
+ 3620 1790 1 508398856 0
+ 4241 1114 1 520652107 0
+ 3556 2810 1 139359541 0
+ 4977 5312 1...

output:

23021982437685
22545059244882
23042129573297
21846100962529
22945110330098
19797328975012
21954507061152
21938547433991
22563458945136
20996830751833
23267340294755
20455062519262
23747613178081
23034064177395
22238967148336
22302781110355
21052961261668
21399336171815
20963685974118
21331296071720
...

result:

ok 50000 lines

Test #31:

score: 0
Accepted
time: 712ms
memory: 24924kb

input:

101000
+ 789 45 1 699137225 0
+ 211 614 1 216996178 0
+ 936 887 1 769728088 0
+ 1 885 1 754680436 0
+ 807 370 1 107909447 0
+ 933 647 1 771120156 0
+ 951 125 1 663155095 0
+ 687 80 1 961858378 0
+ 619 811 1 212401348 0
+ 47 188 1 732924936 0
+ 433 313 1 425771280 0
+ 419 498 1 460805597 0
+ 656 82 1...

output:

22763116566605
22727118596689
1591695865691
21303547820084
5550039547345
389950008909
22074581887268
23212143702543
4999840967043
1672096249923
20481489222160
15916643229052
3937601889029
23254622393816
23162947580053
15329779967830
610975319558
1342327883395
2744701041558
22823414441394
15823998423...

result:

ok 50000 lines

Test #32:

score: 0
Accepted
time: 508ms
memory: 23640kb

input:

101000
+ 73 209 1 294643139 0
+ 32 676 1 844379704 0
+ 47 596 1 813038513 0
+ 38 591 1 655291231 0
+ 96 87 1 12424155 0
+ 81 878 1 53465899 0
+ 90 734 1 70086059 0
+ 88 455 1 550152926 0
+ 54 635 1 80304863 0
+ 45 919 1 964270228 0
+ 90 167 1 94063864 0
+ 9 821 1 323550583 0
+ 20 807 1 628078018 0
+...

output:

22735219955968
23425178960718
23452653687277
24175861017894
23571331067920
23646072416844
24448189134474
22526523982253
22905049545463
23199641100781
23002118400713
22044398366803
23594136940301
772761192740
22232199443974
23452715541655
5378617805460
24175922872272
23494858400419
22711677381556
227...

result:

ok 50000 lines

Subtask #4:

score: 17
Accepted

Test #33:

score: 17
Accepted
time: 781ms
memory: 26332kb

input:

150000
? 5 2 1
+ 4 2 1 783649445 157723097
+ 3 4 1 281409092 43289613
+ 2 3 2 673972686 123253436
? 3 5 3
? 4 2 3
+ 5 5 2 534941804 768558960
+ 2 4 4 103433782 913423755
+ 1 2 3 99618767 608469807
+ 5 4 4 852574365 108454346
? 4 5 5
+ 1 2 4 647253960 383418735
+ 1 5 1 854207792 811999048
+ 4 2 4 995...

output:

0
832128342
783649445
139213677
0
0
0
167523482
0
99618767
673972686
0
99618767
239690802
17392239
0
17819729
99618767
186144480
99618767
17819729
33000376
17392239
17819729
17819729
17392239
0
17392239
17819729
202936106
246793452
30649831
661678130
2404990821
725444736
17819729
725444736
17819729
...

result:

ok 50000 lines

Test #34:

score: 0
Accepted
time: 776ms
memory: 25316kb

input:

150000
+ 1 5 3 181053505 793191895
+ 4 2 1 493318985 9103107
? 4 4 5
+ 5 2 4 92100610 603120383
+ 3 3 5 658647255 433456178
? 1 5 3
+ 2 4 5 132266965 266600955
+ 2 2 4 786423898 415825709
+ 5 3 5 269048583 324793989
? 4 5 4
+ 3 3 4 943550932 385931584
? 1 5 5
+ 3 4 2 725759111 218433242
? 4 5 2
+ 1 ...

output:

493318985
181053505
251778784
181053505
1000644854
0
1535398348
1910038282
438019946
398021309
52410238
52410238
145808484
52410238
52410238
52410238
52410238
2590265894
3778943873
52410238
212567981
1401702149
518523875
3109441395
1144731801
52410238
1670249577
132785052
52410238
52410238
52410238
...

result:

ok 50000 lines

Test #35:

score: 0
Accepted
time: 785ms
memory: 25044kb

input:

150000
+ 5 1 5 953856127 101227648
+ 5 1 5 261469902 652115004
? 4 5 4
? 5 1 3
+ 5 2 1 298076327 230376837
? 5 3 3
? 1 5 1
? 3 4 3
? 4 4 4
? 3 2 1
? 5 5 3
+ 5 3 2 462274692 180309851
? 3 5 4
? 4 4 1
+ 5 3 2 966067618 25434672
+ 2 4 1 126266537 590601692
+ 3 4 5 191427817 837583121
? 5 5 2
+ 3 4 4 25...

output:

0
0
298076327
0
0
0
0
298076327
0
0
851396794
0
126266537
298076327
553249369
0
0
601643517
742307432
785522127
867804616
734894209
854253450
99070489
99070489
0
148636583
178053925
1066817196
402129074
553958629
536615754
292048894
1459202471
292048894
1025899074
437368202
990157425
318164349
99070...

result:

ok 50000 lines

Test #36:

score: 0
Accepted
time: 495ms
memory: 23984kb

input:

150000
+ 3 2 5 90570612 391548206
+ 1 2 2 58771120 203725510
+ 5 3 4 32028449 348390205
? 2 5 4
? 2 3 2
+ 2 5 2 3743369 356202476
+ 3 5 3 26976622 462934526
+ 2 4 3 94122970 535163256
+ 5 5 4 76758956 442107418
+ 1 3 1 27349964 439871720
+ 1 4 3 53141753 823626843
+ 2 3 4 69614961 419234376
+ 3 1 4 ...

output:

58771120
58771120
42165432
16120145
9409553
9409553
9409553
23294931
766906
766906
17414370
766906
0
766906
58771120
23294931
23294931
27349964
766906
49764556
9409553
17414370
766906
766906
27349964
766906
23294931
766906
27349964
13378601
13378601
766906
9409553
13378601
766906
5323599
766906
5303...

result:

ok 50000 lines

Test #37:

score: 0
Accepted
time: 1055ms
memory: 23860kb

input:

150000
+ 1 3 3 236557894 36212845
+ 5 3 2 817453094 16556383
+ 1 4 2 445697793 37050294
+ 1 4 4 814559552 21703515
? 2 1 4
+ 2 3 3 663732636 32677143
+ 3 1 5 268937398 33394795
+ 4 2 1 88648626 510667
+ 5 1 5 550013735 62202793
? 2 1 4
+ 1 3 2 907129048 93675558
+ 4 2 2 556882821 4440203
? 4 3 4
+ 2...

output:

0
0
2285945276
0
0
641091244
3767614924
0
0
4320939119
0
0
3713772670
3102991774
1777197534
1560203758
4628779160
5994488872
735188735
735188735
5521946696
1251443556
1548642225
7587494423
3797979351
735188735
2589834094
3043623377
6163996669
3628140461
4374064880
735188735
3628140461
1452540773
298...

result:

ok 50000 lines

Test #38:

score: 0
Accepted
time: 1084ms
memory: 23796kb

input:

150000
+ 2 4 5 391821177 4365120
+ 1 4 3 611211057 4129990
+ 3 5 4 516990120 8417727
? 2 3 4
+ 2 4 2 846815862 3160173
? 5 3 5
+ 2 3 2 258784121 8182061
? 4 1 1
+ 4 2 4 360891983 3068664
+ 3 2 4 506975707 7411294
? 4 5 4
? 1 5 3
+ 1 5 5 146328856 7636121
? 4 5 5
? 4 1 5
+ 5 1 4 630561331 8831255
+ 2...

output:

0
0
0
3070367605
611211057
3596516397
0
3233997031
1754970732
611211057
2257854397
4765730840
301819216
1866137538
1602302284
1887267398
1626361812
4928054567
1778472010
3689197354
3325673955
2569518872
2569518872
3348100194
4161552519
9209707131
2029558795
550778474
4003682225
14269030295
206928040...

result:

ok 50000 lines

Test #39:

score: 0
Accepted
time: 1094ms
memory: 24848kb

input:

150000
? 3 2 3
+ 5 4 4 162455940 615663
? 3 4 3
+ 3 1 1 673271791 631558
+ 4 4 4 346566084 393621
+ 5 3 5 369626892 826643
+ 5 5 1 209436431 243486
+ 1 1 3 649386400 400467
? 1 1 2
+ 2 2 5 511975030 17529
+ 5 1 4 28307830 991305
? 1 2 5
+ 5 4 2 971013073 350438
? 2 2 3
+ 1 4 5 98470642 365486
? 3 4 ...

output:

0
0
0
649386400
649386400
673271791
1322026633
1322026633
1481135896
1457471491
3658072490
3999934664
2313283377
2313283377
2294149488
808495663
2676491201
2241355276
4073609045
1481135896
808495663
2630267940
1481135896
0
673271791
808495663
1481135896
5531452038
5630058467
808495663
7861521832
859...

result:

ok 50000 lines

Test #40:

score: 0
Accepted
time: 1088ms
memory: 26172kb

input:

150000
? 5 1 2
+ 2 4 5 327361241 23433
+ 2 4 1 675263188 30691
? 2 1 4
? 3 1 2
+ 4 5 5 881248860 68429
+ 1 2 3 879262712 60262
? 4 5 5
+ 1 4 5 328805194 84233
+ 1 1 4 338679283 55374
+ 3 1 2 228670727 32271
? 2 4 3
+ 5 4 2 114661377 63719
? 4 2 4
? 3 2 4
? 5 1 3
+ 1 3 2 621915409 32759
? 4 1 4
? 3 3...

output:

0
0
0
2762976619
1554465638
1446497086
1446497086
228670727
567294636
850553377
1839741768
2601074910
0
1921230208
1378636346
3858830176
1548976257
926904595
81521199
2719336725
2793715668
3248370918
10331960399
5091878565
4018656205
1106388511
3262893898
1729412832
3594643188
2733859705
7932424252
...

result:

ok 50000 lines

Test #41:

score: 0
Accepted
time: 1087ms
memory: 24404kb

input:

150000
+ 5 2 5 164905390 1189
+ 4 1 2 160544216 5067
? 5 5 4
+ 5 5 3 870866930 508
? 3 1 1
+ 1 1 2 53280044 7699
+ 3 5 4 560201537 2409
+ 4 1 2 706436159 1197
? 3 4 4
+ 5 2 4 658781274 2619
+ 2 5 3 923032794 4146
? 1 4 2
? 5 3 4
+ 5 4 1 191303980 1812
+ 3 4 2 524428773 4246
? 5 2 1
+ 5 3 1 177512849...

output:

160544216
0
53280044
53280044
1579026308
0
920247653
810463761
2464354948
810463761
3110400209
755304382
2920384499
2528730650
2855933227
2053410388
3837722898
9757857458
11850356142
663793297
663793297
8985294866
663793297
15350757792
1945172602
5633968344
5056697909
1305915765
3769326910
243187425...

result:

ok 50000 lines

Test #42:

score: 0
Accepted
time: 538ms
memory: 24344kb

input:

100100
+ 5 4 4 295533863 770267023
+ 5 2 5 110055486 184970381
+ 3 3 2 507487407 789383364
+ 3 1 5 366089023 322735702
+ 1 5 5 337528805 619452237
+ 2 5 3 970382466 188020625
+ 2 4 4 765064153 509816572
+ 3 5 1 790366355 128444510
+ 1 3 2 508533206 927735458
+ 2 4 2 530262220 557375070
+ 3 2 1 39592...

output:

41619526892
47307955248
3245592453
23104548033
16654267972
14955652614
46989708673
61008376811
18998737283
47307955248
15461938471
79183
32442030914
79183
32442030914
79183
54805183217
17478402709
15341565528
37704000590
15341565528
31615192957
19052226048
56997750156
21346796058
18998737283
1899873...

result:

ok 50000 lines

Test #43:

score: 0
Accepted
time: 733ms
memory: 23268kb

input:

100100
+ 4 4 2 506094788 21119848
+ 1 1 4 864921694 95137378
+ 3 1 3 904533236 22072657
+ 1 5 4 887301128 47189419
+ 3 5 2 846688771 2080579
+ 3 2 4 563370925 32330299
+ 4 4 2 67650919 53167458
+ 1 3 4 664946877 31264863
+ 1 4 2 777057720 19149526
+ 1 3 1 671793784 24464268
+ 2 1 3 213961099 8302000...

output:

5318310323124
6486139657184
10723984834672
1790599121213
3217175861180
8095749961447
2144576439169
3212498341397
3182152574404
8003165093573
1095560899332
3613191114671
7214669294842
4277626017491
1418650318318
3615716163463
2902888213021
1095560899332
8095749961447
1635532701883
1416274890242
32171...

result:

ok 50000 lines

Test #44:

score: 0
Accepted
time: 602ms
memory: 23480kb

input:

100100
+ 3 1 5 106571767 521124
+ 5 5 2 798071075 136452
+ 3 5 4 285937876 713992
+ 3 2 4 630079186 243691
+ 1 3 3 914361110 77065
+ 3 3 3 557429860 270518
+ 5 4 3 960145125 100250
+ 1 5 3 886032983 289543
+ 1 1 4 824479843 424404
+ 3 5 3 703963752 516644
+ 5 1 5 209427120 420896
+ 4 4 5 841911429 1...

output:

9619523542443
7912331213534
12004647629485
7226933315752
12803115668854
9968817102673
7991674151424
6357638239230
4772372512273
11958026756745
9619523542443
1646175823552
3610812784959
2357054011221
16021191380763
5954454824032
20031390403929
7912331213534
4762615403265
7193315293188
4008119828454
3...

result:

ok 50000 lines

Test #45:

score: 0
Accepted
time: 746ms
memory: 22152kb

input:

100100
+ 3 3 5 22165400 11946
+ 5 4 4 552937282 88165
+ 3 2 2 19420193 64340
+ 1 5 4 151291290 8566
+ 2 3 2 759957564 1428
+ 4 4 2 855451029 22062
+ 2 5 3 557699183 21522
+ 4 2 3 424177016 15876
+ 4 2 5 682938940 34625
+ 1 3 3 140462606 79238
+ 2 3 2 752391930 42611
+ 1 1 5 144928750 57095
+ 2 5 5 2...

output:

6000096641890
2042584301737
8025033842142
3221939479636
15074268840707
3629077360898
2968393877210
10047063861083
6102619816596
8028791153237
15930402931714
11992397269075
6102619816596
3221939479636
12746046250166
1596573577065
4773608144512
1163440505164
1207388386205
11936029307556
4793547647383
...

result:

ok 50000 lines

Test #46:

score: 0
Accepted
time: 742ms
memory: 22388kb

input:

100100
+ 1 3 5 213133712 6071
+ 2 5 1 30814700 2169
+ 3 1 2 983186508 1720
+ 1 5 5 967668684 3043
+ 5 1 2 857308260 5920
+ 1 5 1 105916521 77
+ 4 1 4 859212833 1127
+ 4 5 5 766518052 7988
+ 1 5 3 204895703 274
+ 3 3 3 212095728 4461
+ 2 5 2 969868248 6646
+ 2 3 5 140873247 4859
+ 1 3 5 266397825 529...

output:

4737647415446
3171942890542
958967875190
11879068313267
5896984396788
2032656602447
2363369017059
15120442874266
3930880637897
7959148168769
5975180778434
1171618476349
20051532537074
3562450732043
9547118966028
12039843554879
3165706824551
7960878274482
11879068313267
1948801625722
4769536277515
49...

result:

ok 50000 lines

Subtask #5:

score: 30
Accepted

Test #47:

score: 30
Accepted
time: 656ms
memory: 24044kb

input:

150000
+ 9842 1 1 26088315 73696334
+ 2239 1 1 340356927 653719371
+ 349 1 1 632186088 849099938
? 908 1 1
+ 5153 1 1 487261860 697113681
? 984 1 1
+ 5694 1 1 800262114 571078829
? 1152 1 1
+ 3322 1 1 855670925 826813576
+ 8218 1 1 45843349 617723019
+ 3988 1 1 641119549 840483348
+ 3253 1 1 1654789...

output:

632186088
632186088
632186088
632186088
45843349
632186088
165478900
165478900
165478900
89532850
632186088
45843349
781393803
217229655
164632714
1252158199
1094814425
905809339
781393803
990240153
178676040
781393803
1357387778
1387689226
1909056585
1825681237
1387689226
1409049408
2447699693
2140...

result:

ok 50000 lines

Test #48:

score: 0
Accepted
time: 657ms
memory: 25068kb

input:

150000
+ 1042 1 1 725262009 13135868
+ 5930 1 1 772071356 1763976
+ 2659 1 1 960987606 556806643
? 6107 1 1
? 4790 1 1
+ 4533 1 1 962088798 967161500
+ 4691 1 1 533777434 90978483
? 1929 1 1
+ 6319 1 1 508842421 265626658
+ 5347 1 1 498177159 469352662
? 9736 1 1
+ 7141 1 1 241912119 607985082
+ 798...

output:

1888378460
1129442972
725262009
2598144969
1931135515
199435231
2010258134
161623090
1183652664
161623090
161623090
1758212342
161623090
161623090
161623090
284253756
3898122725
4203959001
2426320434
2933976154
2501412469
420154293
824335256
1846416582
1767865696
339846132
333654016
4168542013
69471...

result:

ok 50000 lines

Test #49:

score: 0
Accepted
time: 667ms
memory: 25048kb

input:

150000
+ 2242 1 1 129468410 247542693
+ 9621 1 1 245254980 644775873
+ 8074 1 1 658385344 674578765
+ 2972 1 1 125620964 897545589
+ 3764 1 1 49267806 43723988
+ 3699 1 1 242281917 302139684
+ 5378 1 1 412716744 991210558
+ 4067 1 1 884710297 203483115
+ 3044 1 1 507568888 655543677
+ 991 1 1 163728...

output:

0
122688167
129468410
59201670
163728451
5112874
5112874
5112874
0
129468410
129468410
8991930
8991930
1210551
1210551
1210551
8991930
1210551
1210551
1210551
0
1210551
1210551
1210551
1210551
5112874
1210551
8991930
1210551
1210551
1210551
1210551
8991930
1210551
5112874
1210551
1210551
8991930
0
1...

result:

ok 50000 lines

Test #50:

score: 0
Accepted
time: 500ms
memory: 24280kb

input:

150000
+ 7549 1 1 73538252 201514551
+ 4388 1 1 53077340 600766608
? 5695 1 1
? 4982 1 1
+ 8809 1 1 4321029 675536210
? 1753 1 1
+ 643 1 1 31602644 123319600
? 2905 1 1
+ 3431 1 1 92485628 974098813
? 3686 1 1
? 5323 1 1
? 9354 1 1
+ 8268 1 1 58636158 164191193
+ 8636 1 1 21538569 477799343
? 6962 1...

output:

53077340
53077340
0
31602644
31602644
31602644
4321029
31602644
31602644
4321029
13156871
13156871
13156871
13156871
3038272
7569007
7569007
7569007
3038272
7569007
3038272
3038272
3038272
7569007
7569007
3038272
3038272
3038272
3038272
3038272
3038272
7569007
15690783
3038272
3038272
3038272
756900...

result:

ok 50000 lines

Test #51:

score: 0
Accepted
time: 805ms
memory: 24896kb

input:

150000
+ 2921 1 1 751469159 3159596
+ 6821 1 1 810113963 2762719
+ 2647 1 1 632021931 54015134
+ 7124 1 1 875250923 13955061
? 3576 1 1
? 6492 1 1
+ 9695 1 1 129133684 39378408
? 2144 1 1
? 8725 1 1
+ 6698 1 1 95703367 84673794
+ 2388 1 1 259879453 68786454
+ 5236 1 1 900919382 19953441
? 1363 1 1
+...

output:

1329475956
1329475956
0
2997726185
0
5660164979
0
2854145261
3276791010
7503616044
6017692630
8741960152
3994909222
11051022864
6482136909
14389283286
11136751550
5552964893
180171431
12511228695
17052978359
4192308491
21115965645
23272122223
3202942177
5123663941
9549303110
11942730424
22480445809
...

result:

ok 50000 lines

Test #52:

score: 0
Accepted
time: 823ms
memory: 25176kb

input:

150000
+ 8244 1 1 878273743 6656644
+ 1935 1 1 920982899 8235455
+ 4130 1 1 61866981 3571937
? 9664 1 1
+ 7931 1 1 389472261 2365295
+ 9472 1 1 701460891 2871340
? 2155 1 1
? 4895 1 1
+ 6719 1 1 112105816 1613750
+ 3966 1 1 625745142 1371575
? 5763 1 1
? 9241 1 1
+ 9605 1 1 222911378 9301215
+ 2313 ...

output:

1846231524
920982899
974614425
1596787630
2966003761
1736795315
2876530587
2876530587
2876530587
0
3392884256
5928670216
4967425974
6409286779
4967425974
7281109524
11131596596
9030776185
5638331272
969315216
969315216
5640807095
11218987647
14180232895
12874462957
7117427980
16149130045
17067223458...

result:

ok 50000 lines

Test #53:

score: 0
Accepted
time: 833ms
memory: 26124kb

input:

150000
+ 2958 1 1 769599485 33385
+ 9863 1 1 590703085 932749
? 7365 1 1
+ 1185 1 1 275651694 295699
+ 8229 1 1 822254613 643068
+ 7170 1 1 357321372 782605
+ 6900 1 1 749741332 679909
+ 702 1 1 848927465 965380
+ 6469 1 1 147706580 195558
? 6681 1 1
? 4308 1 1
+ 3055 1 1 428308460 690567
+ 963 1 1 ...

output:

769599485
2040428587
1892917565
1709014573
2437030142
2437030142
6270906647
5374334202
6291635134
2437030142
6361243816
6381100576
2718870083
2699013323
8155889115
2699013323
3666884698
9103903730
8495150996
12924470355
8726512833
5716849136
608600603
16029362470
4561026897
19657532871
18245075018
0...

result:

ok 50000 lines

Test #54:

score: 0
Accepted
time: 836ms
memory: 24060kb

input:

150000
? 7074 1 1
+ 2785 1 1 775263491 16594
+ 2732 1 1 718613248 79530
? 8837 1 1
+ 6376 1 1 29532863 25730
+ 5245 1 1 312857358 13173
+ 7791 1 1 562378366 52971
? 3749 1 1
+ 1566 1 1 705488865 13368
+ 5479 1 1 187937864 52635
+ 8517 1 1 215018625 94013
+ 8175 1 1 499802817 9307
+ 7975 1 1 89882121...

output:

0
1493797209
1493797209
5050354900
2863944428
2863944428
2863944428
1370163813
1370163813
664737663
2279010497
4678151274
5930554897
4678151274
664737663
5169957013
6991628065
7382248197
10699011607
3210310979
24609877549
664737663
20385664169
3210310979
12760653180
13883836038
8659849943
3810464808...

result:

ok 50000 lines

Test #55:

score: 0
Accepted
time: 836ms
memory: 24444kb

input:

150000
+ 6094 1 1 458020405 8674
+ 2402 1 1 698095244 5458
? 8791 1 1
+ 1504 1 1 299996055 2652
+ 6766 1 1 613244525 3269
? 8352 1 1
? 9504 1 1
+ 1939 1 1 486265266 727
? 1906 1 1
+ 8107 1 1 84971704 4372
+ 4839 1 1 940660624 6629
? 3081 1 1
+ 4125 1 1 188647436 3909
? 4317 1 1
+ 3801 1 1 149149508 ...

output:

1156106975
2069338828
2069338828
299996055
1484348455
1672991982
3919015077
786258669
1484348455
3799792115
2261308115
6784560904
3160590277
5581683737
9928386943
6193720727
0
533650293
1319905672
8940939989
7434224171
2083183896
9377886821
8112653865
1319905672
11682190390
8045785082
8473667457
236...

result:

ok 50000 lines

Test #56:

score: 0
Accepted
time: 829ms
memory: 26156kb

input:

150000
+ 820 1 1 899382536 143
? 9075 1 1
? 7405 1 1
+ 3754 1 1 976267586 794
+ 1220 1 1 583413101 854
? 1638 1 1
+ 168 1 1 448728328 437
+ 4626 1 1 552854071 170
+ 4083 1 1 153774339 563
+ 4041 1 1 491024540 683
+ 1966 1 1 232528086 839
? 2128 1 1
+ 2858 1 1 409617501 127
+ 171 1 1 421110567 564
? ...

output:

899382536
899382536
1482794783
2164049921
4615841707
5168695608
5168695608
3143557174
8255151727
12344862606
869838331
4064232372
11349340275
16779663374
3627215348
6945891365
18415078814
15525403408
6126865941
22295503476
7980201692
5079786829
22203159266
0
22673694296
6184527457
8370218817
2927122...

result:

ok 50000 lines

Test #57:

score: 0
Accepted
time: 481ms
memory: 23032kb

input:

101000
+ 9691 1 1 751957849 509242773
+ 3947 1 1 944391008 216028468
+ 7520 1 1 784141986 340672667
+ 257 1 1 889356759 256047340
+ 3047 1 1 785947758 428737450
+ 2247 1 1 212847423 550449143
+ 6564 1 1 816884040 278074741
+ 7142 1 1 158463113 762443178
+ 8566 1 1 204639960 526474638
+ 2239 1 1 6677...

output:

65622895685
71173852784
70363663116
69302094249
61236373513
81943224661
81088348265
80012903726
85867860277
66934824358
74003992267
68048809881
74526246441
926175
92260440247
64134162467
72031952719
85867860277
78094542433
71436213883
3481
74216576398
71979913254
73712024907
74396329936
78025506188
...

result:

ok 50000 lines

Test #58:

score: 0
Accepted
time: 471ms
memory: 25156kb

input:

101000
+ 307 1 1 50959357 687004455
+ 4975 1 1 45666491 196941552
+ 7271 1 1 47884496 723742323
+ 3975 1 1 74952570 183067399
+ 3994 1 1 725428 304288179
+ 6326 1 1 99265031 63099835
+ 7467 1 1 60346287 709721177
+ 220 1 1 69208673 881840165
+ 866 1 1 8657124 198485025
+ 8901 1 1 92471807 385115089
...

output:

263
263
263
263
263
263
263
263
263
1968
263
263
263
263
263
1968
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
263
1968
263
263
263
263
263
263
263
1968
263
263
263
263
263
263
263
263
263
263
263
263
263
1968
263
263
263...

result:

ok 50000 lines

Test #59:

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

input:

101000
+ 1720 1 1 392352931 32700938
+ 9050 1 1 511742880 76434699
+ 1750 1 1 323029566 43885857
+ 1704 1 1 75816143 97711411
+ 1974 1 1 305590816 61051769
+ 5756 1 1 763806330 70699727
+ 1742 1 1 210314364 52677017
+ 2853 1 1 869926493 51729323
+ 7924 1 1 772971063 82156595
+ 8027 1 1 677086267 430...

output:

21594842420172
20230554806782
20777889671575
21885964333927
20482927795322
9587612818559
21186791033826
21969713322713
263730888723
15724614498857
21297909676532
21455219768765
21511782461515
21387717780780
21547866935483
21808631420474
12349789606076
6389853993719
9990847391965
12384812200096
21640...

result:

ok 50000 lines

Test #60:

score: 0
Accepted
time: 498ms
memory: 22844kb

input:

101000
+ 3202 1 1 457362315 7802653
+ 2466 1 1 504782602 3435455
+ 1146 1 1 667915195 4895544
+ 3323 1 1 28435751 1042891
+ 3101 1 1 993614764 7600590
+ 3154 1 1 237227228 1318172
+ 8974 1 1 834523413 8753390
+ 4489 1 1 769525295 6976866
+ 7382 1 1 140720835 4701660
+ 3646 1 1 27793261 293985
+ 2884...

output:

23007132635900
23953811569945
23478630203485
22580941163143
23854019855303
22769227349162
21773018664717
22960013287439
22416721482751
21958354408086
22194896067028
22951061490607
22046937020398
24016505020583
21774370508084
22845662233482
22544157362639
22178355495849
21812251045268
10182155561606
...

result:

ok 50000 lines

Test #61:

score: 0
Accepted
time: 569ms
memory: 25088kb

input:

101000
+ 5231 1 1 466353618 883092
+ 1762 1 1 72134474 955636
+ 3888 1 1 206802775 471654
+ 4770 1 1 551331625 690570
+ 7835 1 1 734596185 507421
+ 3959 1 1 788186135 18695
+ 9560 1 1 227953737 464412
+ 7496 1 1 554617602 214193
+ 9445 1 1 709051939 677460
+ 3626 1 1 332144436 48725
+ 490 1 1 685898...

output:

14687035468285
23555242777681
22889552295763
9479571789628
1301403014275
22837891237854
24155696223622
23610778609745
23417543628655
15214377585013
14934049372897
24382178140010
18079556447123
23741658950736
23835449781632
22381685157101
3987304162651
23448526675552
18286462045706
13821985526950
224...

result:

ok 50000 lines

Test #62:

score: 0
Accepted
time: 497ms
memory: 22688kb

input:

101000
+ 3065 1 1 718428646 62499
+ 5313 1 1 375057895 19319
+ 5954 1 1 562901572 5920
+ 8712 1 1 253583004 96650
+ 7202 1 1 697360750 30450
+ 8250 1 1 360510854 4849
+ 169 1 1 802095353 57021
+ 6647 1 1 123707530 88996
+ 2788 1 1 952819249 62661
+ 9263 1 1 425734691 16053
+ 9660 1 1 834189890 30057...

output:

24198981175201
11419627930444
22265846550387
23337409105853
22630199131957
23520709991163
21278504617396
24158085531736
24032499963388
23581830405969
23696884098132
23395623560935
23085985485691
22687142677318
22054218612074
23860106881407
23427809677198
23738398791690
22391721717674
24314434465067
...

result:

ok 50000 lines

Test #63:

score: 0
Accepted
time: 565ms
memory: 23240kb

input:

101000
+ 5095 1 1 358823729 2621
+ 3121 1 1 311005987 954
+ 184 1 1 101789152 7667
+ 159 1 1 145075097 5725
+ 1936 1 1 848407588 5608
+ 1759 1 1 280065980 4094
+ 2243 1 1 859089188 776
+ 9653 1 1 908799838 1911
+ 1747 1 1 226183060 7624
+ 7755 1 1 66522355 8332
+ 7266 1 1 702052304 6229
+ 3205 1 1 4...

output:

22664392787526
23000801372372
958807971529
20359274633329
17893873833625
8919454449639
6910357746496
9545678558452
6793097850614
24122583503099
23552063550983
24416961197332
15563930086697
22391074708005
9439029933394
18745583592618
12051361830269
16308636826163
16527706880398
10791143867224
2330271...

result:

ok 50000 lines

Test #64:

score: 0
Accepted
time: 572ms
memory: 23200kb

input:

101000
+ 2594 1 1 41786839 871
+ 7407 1 1 6674973 561
+ 2239 1 1 679440501 965
+ 677 1 1 488839723 628
+ 3710 1 1 346668643 441
+ 7105 1 1 409095425 616
+ 7009 1 1 563608691 1000
+ 3621 1 1 444580471 619
+ 5310 1 1 47299691 84
+ 7330 1 1 390068726 195
+ 3530 1 1 369810515 719
+ 6449 1 1 972745562 20...

output:

22300549908344
17289464803638
23315500358374
22248442029313
23704756066786
23548617918523
23369707071233
22090844220029
1879415750205
24291434674655
16189229439086
23326429887755
22066691422871
6120077837096
24279468344146
12631927212993
8902845445010
24299295301438
22986507871555
5783794554079
1457...

result:

ok 50000 lines

Subtask #6:

score: 33
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #65:

score: 33
Accepted
time: 829ms
memory: 25312kb

input:

150000
+ 2136 5200 4695 73806388 275279552
+ 7425 1677 6452 747823216 220081428
+ 5013 7572 6666 923027421 502469808
? 3242 8471 4530
+ 983 8109 1085 38721894 658277766
+ 1460 2929 4717 88739823 17455381
? 6331 1950 7990
+ 6681 2693 8872 171556673 240160639
+ 5037 9482 8117 427666714 825732292
+ 780...

output:

0
0
0
202043176
426365180
924819539
352415932
0
0
38721894
0
894851834
0
0
0
214891162
1507843402
73806388
0
540520601
73806388
214891162
1495048752
320140700
1854803020
747741631
353374440
0
2201775898
0
0
2437679013
0
214891162
29649883
214891162
38721894
554317687
214891162
214891162
734255859
29...

result:

ok 50000 lines

Test #66:

score: 0
Accepted
time: 829ms
memory: 25088kb

input:

150000
+ 3336 6452 2822 478012790 583315305
+ 1116 8957 3615 221006841 568126033
? 8771 2183 1328
+ 1145 2105 5691 722379076 422551076
+ 8212 2449 3924 46619729 735797124
+ 2955 5391 2458 504607649 700901348
+ 6949 5675 8032 883820464 338822004
? 255 7447 9649
+ 934 4161 6921 460371466 152429960
? 4...

output:

0
0
0
0
0
0
0
26601504
0
0
163026072
46763596
269455320
119437588
46763596
46763596
46763596
0
0
31627876
26601504
31627876
0
488427971
821398060
675928334
26601504
79457076
0
1299073886
26601504
884812984
0
0
26601504
544558553
0
0
26601504
251221134
26601504
134868035
0
0
26601504
163026072
266015...

result:

ok 50000 lines

Test #67:

score: 0
Accepted
time: 832ms
memory: 25052kb

input:

150000
? 949 384 8538
+ 779 5068 2319 597467839 112128890
? 6113 7511 4748
+ 4148 2737 8292 642125883 949226677
? 6383 6344 1548
+ 2520 8544 9494 499677008 980888638
+ 5443 7154 558 965731903 994104404
+ 426 6617 2861 630400291 61164354
? 2146 2341 9497
+ 2950 9535 327 998470853 198108927
+ 1815 259...

output:

0
597467839
0
0
0
0
1048946928
385804678
0
0
356806800
0
1650376538
0
0
1258191582
2042219315
0
990670791
0
1262106597
288964914
0
0
480113636
137845028
467976239
13284084
325218729
0
480113636
2198073026
179071198
812397343
649087838
9256719
395939580
1634606884
0
0
0
13284084
600020089
600020089
1...

result:

ok 50000 lines

Test #68:

score: 0
Accepted
time: 838ms
memory: 23412kb

input:

150000
+ 5736 3547 1780 949989105 462194372
+ 1202 4732 7943 420872186 559182536
+ 8152 2500 8388 646624415 445720757
+ 4161 6511 55 817987503 489270671
+ 5332 4663 1581 962769956 954406859
+ 5773 3426 8649 479296654 707649448
+ 4251 8499 6284 268901432 919362803
+ 7710 4531 4839 142261786 889553322...

output:

0
962769956
142261786
0
0
366480932
0
342471124
494178646
368632896
2708560449
2061817001
0
2199893914
0
0
47782580
0
435274336
254037574
0
0
2438835364
36822909
0
54024802
124705840
0
1188941261
2980750904
606250486
786813150
36822909
54024802
36822909
1374583410
124705840
127108459
191714210
21999...

result:

ok 50000 lines

Test #69:

score: 0
Accepted
time: 828ms
memory: 23660kb

input:

150000
+ 6936 4798 1395 649162798 65197416
? 7811 5065 5094
? 1090 4893 4716
? 2116 5900 315
+ 2446 5254 1922 966790303 829053412
+ 2614 8810 9663 630475072 218022672
+ 2897 2847 5483 375938065 857999786
? 2642 7729 67
+ 5754 2193 9005 692551093 438467335
+ 6117 9841 9684 416232141 304987630
+ 5813 ...

output:

649162798
0
0
0
0
947631265
0
0
0
484728582
0
307016451
0
966790303
0
0
487672971
0
0
0
0
0
0
735646757
0
0
0
652173479
91659225
913507136
913507136
2661836099
913507136
0
0
91659225
1922065268
2198657823
913507136
1145170518
1798459698
891946127
913507136
837867045
1257468120
49031197
49031197
9135...

result:

ok 50000 lines

Test #70:

score: 0
Accepted
time: 569ms
memory: 26380kb

input:

150000
+ 2195 8548 3610 34515187 432202375
+ 9654 5276 3246 58178067 627597204
+ 6044 1164 3568 99588634 740835376
+ 6003 5732 2128 43626844 400318326
? 3725 8814 9271
+ 3108 5270 8150 68810138 307120398
+ 26 7734 4255 44554300 525876511
? 7120 9709 6619
+ 6752 6993 985 98418315 410927450
+ 1146 672...

output:

34515187
34515187
0
44554300
0
0
0
0
28558379
33386057
33781269
33781269
0
33781269
27563949
54514470
15327354
13783556
44554300
15327354
15327354
54514470
0
15327354
11316186
6500160
54514470
15327354
11316186
15327354
15327354
0
44985242
15327354
14932142
6500160
15327354
0
468261
15327354
5451447...

result:

ok 50000 lines

Test #71:

score: 0
Accepted
time: 540ms
memory: 25796kb

input:

150000
+ 9215 7204 9921 6805008 97686935
+ 5054 3444 8398 3761218 137563562
+ 1669 2393 8411 4526741 503784734
+ 1964 3666 9463 7974670 126133405
+ 4593 5616 3175 8923536 706677662
+ 5154 2392 5552 5793165 675326380
+ 2875 1250 170 4604985 859585349
? 7006 7779 2124
? 7973 3621 3066
+ 7813 7527 1925...

output:

4604985
4604985
4604985
0
1144866
1144866
1144866
4604985
4604985
1590255
1590255
0
4604985
0
0
1590255
1144866
1144866
4604985
0
0
482903
4730535
482903
4604985
0
0
187001
482903
250414
4730535
187001
4604985
482903
0
1144866
187001
187001
4052647
0
482903
2516111
187001
516329
1410713
0
2516111
14...

result:

ok 50000 lines

Test #72:

score: 0
Accepted
time: 1103ms
memory: 23848kb

input:

150000
+ 1759 4662 795 26681303 88713039
+ 2087 6025 466 376476020 21565079
+ 9845 4055 3160 359020729 72230621
? 5776 1175 3296
? 1113 9654 4802
+ 9390 9106 9396 673786254 26214398
? 3068 6903 5809
+ 9249 7635 1295 787338409 43681638
+ 4304 7272 6025 788487187 15203778
+ 8098 5809 5322 625003143 70...

output:

0
0
314444284
702289383
1555013689
262655041
0
376476020
854387879
0
0
0
0
258203692
376476020
1625407854
3701685543
702289383
0
0
0
1688145024
3479936886
0
1017953595
12637097506
376476020
1326883151
258203692
6404630749
0
14185227760
2085181823
0
4324467210
0
14945629555
1059572303
3208455321
2002...

result:

ok 50000 lines

Test #73:

score: 0
Accepted
time: 1128ms
memory: 26068kb

input:

150000
+ 3620 7041 674 835723767 1935861
+ 5970 2303 5698 408568914 9743316
+ 6176 3763 7538 986766474 1349686
+ 7032 1782 732 474030482 4919493
+ 2628 8983 8304 324539053 8757479
+ 1005 9478 5373 953764885 3409553
+ 8945 7348 788 512112471 3436847
? 1735 3976 7253
? 3823 7356 2556
+ 1119 8026 581 6...

output:

0
835723767
1854703061
0
519821865
0
2509650693
0
0
964586965
474030482
988932854
0
0
2259692080
1353609771
964586965
519821865
9126190109
519821865
0
0
0
9836559981
2378199128
10773838954
2129629322
3277173977
6714550359
2332730031
6401760616
6639771604
3222808419
7841003160
224477314
4500282120
28...

result:

ok 50000 lines

Test #74:

score: 0
Accepted
time: 1123ms
memory: 23888kb

input:

150000
? 6093 5929 8749
? 5088 6537 7900
+ 5768 4774 2438 568368897 582045
+ 4552 6295 7044 923031217 773144
? 873 488 4151
+ 4700 4659 4467 853042531 261483
+ 9238 7799 5568 914264657 523722
+ 5378 7537 6373 568185871 431749
+ 6456 8003 1015 834817331 599276
+ 4810 6581 2044 870786180 697397
+ 9589...

output:

0
0
0
0
568368897
0
4731067237
0
991340477
1336760073
991340477
0
2747661742
0
1249029808
991340477
3315404455
2383954825
271003890
2520728169
1986311649
140596470
5591213537
10114965452
0
2187985772
4369964554
4209747277
27894969805
8902453406
9475994419
756937698
1891602561
4885230093
11146288120
...

result:

ok 50000 lines

Test #75:

score: 0
Accepted
time: 1133ms
memory: 24000kb

input:

150000
+ 8916 7779 121 116816357 44984
+ 2268 7670 7331 967015582 9154
+ 6404 7230 2821 940050461 48999
+ 5374 8532 8322 415802529 60044
? 3687 354 1632
? 75 7810 7736
+ 1728 5823 5003 124612361 71250
? 5827 769 6863
+ 918 7441 9787 412497014 26466
+ 6754 3910 3303 668584967 36681
+ 7401 5864 1981 8...

output:

0
0
0
0
0
0
0
2167365293
0
2961207606
0
565378282
0
2390526571
0
0
3309848050
0
1395914100
2076305935
1799578634
577143080
2466736324
348642368
5684119386
624161345
8932412181
0
0
7373723844
54686174
1950938973
8431249988
4318366015
3490783129
0
3764252903
741593398
1984506826
9971151462
4357730341
...

result:

ok 50000 lines

Test #76:

score: 0
Accepted
time: 1134ms
memory: 23796kb

input:

150000
? 5333 1303 7448
? 9866 5583 3197
+ 6967 6595 4562 809426559 420
+ 8298 2389 2972 486534789 8344
+ 8803 7168 8289 579693955 2663
+ 4182 6232 6795 367623592 95
+ 5544 9774 7429 175349692 2119
? 9472 5319 4189
? 6922 6037 8511
+ 1414 5988 1985 707804996 682
+ 4468 8591 5018 86000257 4258
+ 5459...

output:

0
0
486534789
0
0
0
0
0
0
5142516708
2395419566
7027495468
4000081052
4204584454
4526771217
0
5305726795
13900811776
311763032
6879768573
2429053369
4264510131
3549086403
1804423158
991781854
0
5391122627
0
0
0
991781854
6594642752
3085863162
2898115195
16023637139
0
15918624973
0
1408825980
6757934...

result:

ok 50000 lines

Test #77:

score: 0
Accepted
time: 1128ms
memory: 24448kb

input:

150000
+ 5462 7225 263 590648244 921
? 7666 1600 2246
+ 6730 3790 9053 950390429 66
+ 6998 9034 3815 827754025 191
+ 2715 8090 5782 349377276 268
+ 6152 2061 3769 101793198 546
+ 5809 7648 9250 745268470 729
+ 5957 6221 9543 431150825 625
+ 3074 8800 48 127833448 328
+ 2818 4581 1073 525817236 594
+...

output:

0
0
0
116079432
567487154
2014460422
921519046
1295979979
1149129474
11487690680
313599829
3417126329
3934171871
6125901121
3157421710
0
1487347386
4002523336
5158779434
1464233692
2802390188
0
2050037258
0
0
0
4838143747
0
0
8802646949
15958633635
23433998262
4511150462
2068142341
1820221306
296355...

result:

ok 50000 lines

Test #78:

score: 0
Accepted
time: 1117ms
memory: 24424kb

input:

150000
? 707 3 9113
? 6208 881 950
+ 6084 3310 9549 208244591 97
+ 1288 8317 565 218458905 28
+ 281 1880 3968 64225322 69
+ 9486 8327 2068 875276332 27
+ 3201 6478 292 652618841 0
? 4549 4624 5656
? 5467 9062 2605
+ 5469 3948 2716 150939931 95
+ 7964 8007 5790 232942701 89
? 1997 3806 8009
+ 4521 34...

output:

0
0
64225322
871077718
64225322
215165158
64225322
1121968828
0
5123481274
64225322
5338044877
0
0
2661630400
0
1676213875
64225322
635572222
0
1057483043
860289909
2667886360
2036923086
10012081920
4627075003
2769612002
635572222
3847116290
13940618744
3775796797
4589970807
2251985031
7295459230
95...

result:

ok 50000 lines

Test #79:

score: 0
Accepted
time: 1104ms
memory: 23716kb

input:

150000
? 8389 5209 8144
? 1495 4909 3175
+ 8612 6564 2342 194521683 5
+ 8769 4754 3318 61893722 7
? 4799 1050 477
+ 2147 451 3728 383810273 8
? 5755 2522 4650
? 7857 5782 4051
? 5378 6658 7479
+ 5495 6270 2215 623691153 5
? 8410 666 5140
+ 9950 4607 6267 384141451 2
+ 7031 3106 8183 811719113 1
? 82...

output:

0
0
0
383810273
383810273
383810273
383810273
0
383810273
383810273
0
2520770
0
1007501418
383810273
0
383810273
0
5829961409
0
1038943353
3186432315
0
780896716
1819840061
6301481463
1338800081
0
1819840061
0
0
0
0
3229686924
2966168274
2966168274
3847917808
0
1666447798
2860652514
780896716
0
7808...

result:

ok 50000 lines

Test #80:

score: 0
Accepted
time: 512ms
memory: 23928kb

input:

101000
+ 9316 7967 8486 385822268 739741351
+ 620 8270 8446 510501909 758392869
+ 1418 3443 385 645217420 732678887
+ 9710 6468 3189 801280581 52590513
+ 2998 6124 7207 346570001 193295437
+ 8604 1810 3321 292307374 915535238
+ 6236 8253 565 625818554 367101834
+ 8079 3482 1175 186854662 950159179
+...

output:

7553989156
29328
58527
29901
29901
4249372483
29901
29901
5386911418
19625416273
19140963499
29901
29901
29901
58527
58527
58527
29901
10991684584
29901
29901
3962265913
29901
29901
29901
29328
58527
29901
29901
6248550967
29328
58527
29901
11611983396
58527
17713691582
37602616528
29465708466
29328...

result:

ok 50000 lines

Test #81:

score: 0
Accepted
time: 482ms
memory: 24880kb

input:

101000
+ 2894 8312 1801 75589020 277843645
+ 4666 5381 5098 20845341 321853726
+ 948 2277 9973 75449766 777554559
+ 1132 254 4635 37630968 795170481
+ 2824 1251 2497 11643528 176801756
+ 8044 7809 6060 8107052 508101142
+ 3825 5872 1586 94432348 713029577
+ 5951 6177 7301 30755332 558291494
+ 535 11...

output:

246
246
3330
246
3330
3330
246
3330
3330
3330
246
3330
3330
3330
246
246
3330
3330
3330
246
246
3330
246
246
3330
3330
34261
3330
3330
3330
246
246
3330
3330
246
3330
246
246
246
3330
246
3330
246
246
3330
3330
246
3330
246
246
246
3330
3330
246
3330
3330
3330
3330
3330
3330
34261
3330
246
246
3330
...

result:

ok 50000 lines

Test #82:

score: 0
Accepted
time: 547ms
memory: 24264kb

input:

101000
+ 2743 3619 4920 277007292 24451203
+ 4149 5039 1824 272169183 91848491
+ 6084 8553 5807 421733400 79618169
+ 9489 7824 6474 940423881 19712328
+ 3457 3001 8042 732796504 30951228
+ 2136 3188 2176 935782209 51433194
+ 407 3025 6250 919892257 81557325
+ 8253 2809 6278 163862272 76359394
+ 9812...

output:

17121882096413
18581804135485
16633211951896
17974758580665
18514504528751
17406872233000
19375249624415
16779862264489
20178133252201
17075380688547
17605235126283
19562632256962
18368427010632
19296958613905
18226430523315
20658629884075
18751296236152
18509694202963
18655563483748
18789007546846
...

result:

ok 50000 lines

Test #83:

score: 0
Accepted
time: 962ms
memory: 25120kb

input:

101000
+ 4773 1534 1085 622435084 8820608
+ 6149 1399 7967 839521056 8253858
+ 5722 7048 4671 329217201 1983208
+ 936 297 5289 168352462 1834167
+ 896 6781 3715 842374146 5702273
+ 8349 4348 5101 855337335 9737667
+ 2481 644 26 313322580 7771031
+ 1259 4315 9260 948954580 247774
+ 9171 9783 5374 660...

output:

10781587653594
20880009529800
19095877657566
20328924329093
21120555503931
2623833221252
22666823221389
19766074827109
7559417242008
3344813470005
502678856916
3020556408
21817003824716
20277333140509
18129407636542
4331095161052
9768859210556
11077981435449
22289003865825
597562906669
646505750252
...

result:

ok 50000 lines

Test #84:

score: 0
Accepted
time: 555ms
memory: 22296kb

input:

101000
+ 4802 6669 5662 692526184 583179
+ 204 1734 7511 501632646 120711
+ 3197 4645 3066 423851320 721208
+ 6749 4134 9413 13957386 849712
+ 3543 5101 873 552012822 979884
+ 5305 2159 409 229917593 418062
+ 2628 2019 8532 99640274 76217
+ 1410 760 3695 662228542 546498
+ 3007 7199 2294 58712430 61...

output:

19155021921594
22172601638473
22419833279070
21713280216860
20685449953854
20307982379754
20645648991200
131949080024
20809139650289
20262574473862
20548000346606
21072992079016
20306319569501
22431313260584
20644423721375
20800239794780
22226006961126
22354629820531
23043790195440
20605840859470
19...

result:

ok 50000 lines

Test #85:

score: 0
Accepted
time: 989ms
memory: 25032kb

input:

101000
+ 6831 7288 4531 701517487 27834
+ 8012 4990 3654 68984518 71581
+ 5939 3140 1930 962738901 72449
+ 8196 9311 933 610482188 16474
+ 5573 8881 3842 366623172 96744
+ 6110 1831 3334 780876500 92179
+ 3214 6935 5013 788037891 17711
+ 4416 5370 869 152353557 83424
+ 2365 7175 2510 627043534 88378...

output:

22025812127907
1809751814214
19851098674385
5204460114568
1002681299524
19910358752198
21019671354393
19229316571678
22290564139080
2143747645686
21671450374538
21627208314279
2322761257115
20065702184820
21664744503998
2745344682442
1937930980291
23093284195528
21848139159295
21820029729987
4376582...

result:

ok 50000 lines

Test #86:

score: 0
Accepted
time: 571ms
memory: 22632kb

input:

101000
+ 556 115 9278 386723385 1113
+ 9603 7421 4975 771207101 8280
+ 5097 4608 7935 30725176 3943
+ 3059 7073 225 169898608 9293
+ 235 5229 4126 264600004 5351
+ 84 6200 7206 917110654 3367
+ 135 7006 989 375660501 1939
+ 2465 5473 4762 380726157 6984
+ 399 4335 1962 403251483 3856
+ 9685 297 3099...

output:

19717343669310
23335593799885
21470171317803
22205347658758
19010936680939
21378684370990
22242325957391
20808660796679
20508615928705
21603788239059
21608667905605
20103439483945
21911881052970
20375064207795
1066121594150
22219352992770
19726282681969
19957652943760
19078154790818
19717022060157
2...

result:

ok 50000 lines

Test #87:

score: 0
Accepted
time: 1040ms
memory: 25028kb

input:

101000
+ 2585 8030 2739 322085760 382
+ 7411 1078 8414 338558973 535
+ 9326 398 6798 569612757 924
+ 4506 3738 9041 356357993 683
+ 7674 497 9799 5581426 854
+ 889 7360 131 468069560 292
+ 9505 7729 7469 769090826 942
+ 5471 6978 9232 165818464 360
+ 2462 4311 6370 340178805 558
+ 2769 9083 3019 585...

output:

21683243746555
21246129375001
21585294129808
2999020761246
2977045940204
2002194876806
43947713061
22711104949834
22463250011178
567459830724
21963452367883
7646071772719
20393906157849
21160812772973
669682034083
5904976202752
1591232041049
1414823777167
843586489640
19988795180809
19602103184774
2...

result:

ok 50000 lines

Test #88:

score: 0
Accepted
time: 965ms
memory: 24820kb

input:

101000
+ 7375 5878 6212 5428281 65
+ 2761 3745 4871 300707599 25
+ 5579 7867 6006 861586741 73
+ 9231 2630 4008 255641332 56
+ 9333 1087 1768 120075450 52
+ 5169 8598 3214 534436385 98
+ 8673 3292 5062 268700274 100
+ 7685 8990 4423 68925979 89
+ 3023 3508 8887 847731551 9
+ 4151 2127 4192 146311725...

output:

20938285399515
18884066546544
990165752634
19889177762316
3529435673854
20933303510959
19406798439254
989796447140
20746388220255
20043377142679
19971102856968
791283712902
26134899212
457546058287
3132010502930
20226351119325
7314961114118
236531063716
4462461486969
22967394866546
8314859394739
323...

result:

ok 50000 lines