QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#822467#9809. The Grand ContestDeltaxAC ✓507ms71592kbC++144.8kb2024-12-20 13:01:552024-12-20 13:01:56

Judging History

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

  • [2024-12-20 13:01:56]
  • 评测
  • 测评结果:AC
  • 用时:507ms
  • 内存:71592kb
  • [2024-12-20 13:01:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mkp make_pair
#define fi first
#define se second
typedef long long LL;
template <class T>
inline void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	x = x * f;
}

const int MAXN = 4e5;
struct sub {
	LL c;
	int a, b, d, fk;
}a[MAXN + 10];

int w[MAXN + 10];
LL t[MAXN + 10];
map <int, int> mp[3];
struct SEG {
	LL mx[MAXN * 4 + 10], tag[MAXN * 4 + 10];
	void pushup(int s) {
		mx[s] = max(mx[s << 1], mx[s << 1 | 1]);
	}
	void pushdown(int s) {
		tag[s << 1] += tag[s];
		mx[s << 1] += tag[s];
		tag[s << 1 | 1] += tag[s];
		mx[s << 1 | 1] += tag[s];
		tag[s] = 0;
	}
	void build(int l, int r, int s) {
		tag[s] = mx[s] = 0;
		if (l == r) return;
		int mid = l + r >> 1;
		build(l, mid, s << 1);
		build(mid + 1, r, s << 1 | 1);
	}
	void upd(int l, int r, int L, int R, LL v, int s) {
		if (L > r || R < l) return;
		if (L <= l && r <= R) {
			mx[s] += v;
			tag[s] += v;
			return;
		}
		pushdown(s);
		int mid = l + r >> 1;
		upd(l, mid, L, R, v, s << 1);
		upd(mid + 1, r, L, R, v, s << 1 | 1);
		pushup(s);
	}
	int q1(int l, int r, int x, LL v, LL &d, int s) {
		if (mx[s] < v) return -1;
		if (r < x) return -1;
		if (l == r) {
			d = mx[s];
			return l;
		}
		pushdown(s);
		int mid = l + r >> 1;
		int tmp = q1(l, mid, x, v, d, s << 1);
		if (tmp == -1)
			return q1(mid + 1, r, x, v, d, s << 1 | 1);
		return tmp;
	}
	int q2(int l, int r, int x, LL v, LL &d, int s) {
		if (mx[s] < v) return -1;
		if (l > x) return -1;
		if (l == r) {
			d = mx[s];
			return l;
		}
		pushdown(s);
		int mid = l + r >> 1;
		int tmp = q2(mid + 1, r, x, v, d, s << 1 | 1);
		if (tmp == -1)
			return q2(l, mid, x, v, d, s << 1);
		return tmp;
	}
}seg;

inline void chkans(pair<LL, LL> &ans, LL L, LL R) {
	if (ans.fi == -1) ans = mkp(L, R);
	LL tmp = ans.se - ans.fi;
	if (tmp > R - L) ans = mkp(L, R);
	if (tmp == R - L && L < ans.fi) ans = mkp(L, R);
}

signed main() {
	//freopen ("std.in", "r", stdin);
	//freopen ("std.out", "w", stdout);
	int T; read(T);
	while (T--) {
		int n, p;
		read(n); read(p);
		mp[1].clear(); mp[2].clear();
		for (int i = 1; i <= n; ++i) {
			a[i].fk = 0;
			read(a[i].a); read(a[i].b);
			read(a[i].c); read(a[i].d);
			t[i] = a[i].c;
		}
		int dt = 0; LL dp = 0;
		//sort(a + 1, a + n + 1, cmp);
		for (int i = 1; i <= n; ++i) {
			int ty = a[i].a == 1? 1 : -1;
			if (mp[a[i].a].find(a[i].b) == mp[a[i].a].end()) {
				if (a[i].d == 0) dt += p * ty;
				else {
					a[i].fk = 1;
					dp += ty;
					dt += a[i].c * ty;
					mp[a[i].a][a[i].b] = 1;
				}
			}
		}
		for (int i = 1; i <= n; ++i) {
			int ty = a[i].a == 1? 1 : -1;
			if (mp[a[i].a].find(a[i].b) == mp[a[i].a].end()) {
				if (a[i].d == 0) dt -= p * ty;
			}
		}
		if (dp) {
			printf("-1\n");
			continue;
		}
	//	cerr << dt << endl;
		if (dt <= 0) {
			dt = (-dt) + 1;
			for (int i = 1; i <= n; ++i)
				a[i].a ^= 3;
		}
		pair <LL, LL> ans = mkp(-1ll, -1ll);
		int cnt = 0, tt = n;
		int m = unique(t + 1, t + n + 1) - t - 1;

		seg.build(1, m, 1);
		for (int i = m; i >= 1; --i) {
			while (tt > 0 && a[tt].c >= t[i]) {
				if (!a[tt].fk) {
					--tt;
					continue;
				}
				if (a[tt].a == 1) ++cnt;
				else --cnt;
				--tt;
			}
			w[i] = cnt;
		//	cerr << t[i] <<" "<<w[i]<<endl;

			LL d = 0, R;
			int r = seg.q1(1, m, i + 1, dt, d, 1);
			if (r != -1) {
				if (w[r] <= 0) {
					d -= (t[r] - t[r - 1]) * w[r];
					R = t[r - 1];
				}
				else {
					LL tmp = (d - dt) / w[r];
					tmp = min(tmp, t[r] - t[r - 1]);
					d -= w[r] * tmp;
					//LL delta = (d - dt) / (t[r] - t[i]);
					R = t[r] - tmp;
				}
				LL limit = min(R - t[r - 1], t[i] - t[i - 1]);
				LL delta = w[i] - w[r] >= 0? limit : min(limit, (d - dt) / -(w[i] - w[r]));
				chkans(ans, t[i] - delta, R - delta);
				//ans = min(ans, R - t[i]);
			}
			seg.upd(1, m, i, m, w[i] * (t[i] - t[i - 1]), 1);
		}
		seg.build(1, m, 1);
		for (int i = 1; i <= m; ++i) {
			seg.upd(1, m, 1, i, w[i] * (t[i] - t[i - 1]), 1);
			LL d = 0, L;
			int l = seg.q2(1, m, i, dt, d, 1);
			if (l != -1) {
				if (w[l] <= 0) {
					d -= (t[l] - t[l - 1]) * w[l];
					L = t[l];
				}
				else {
					LL tmp = (d - dt) / w[l];
					tmp = min(tmp, t[l] - t[l - 1]);
					d -= w[l] * tmp;
					L = t[l - 1] + tmp;
				}
				LL limit = min(L - t[l - 1], t[i] - t[i - 1]);
				LL delta = w[l] - w[i] >= 0? limit : min(limit, (d - dt) / -(w[l] - w[i]));
				chkans(ans, L - delta, t[i] - delta);
				//ans = min(ans, t[i] - L);
			}
		}
		if (ans.fi != -1) printf("%lld %lld\n", ans.fi, ans.se);
		else printf("-1\n");
	}
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
6 20
1 1 60 0
2 2 60 0
2 2 120 1
1 2 180 1
1 2 180 0
2 2 300 1
2 20
1 1 300 1
2 2 300 1

output:

120 160
-1

result:

ok 3 number(s): "120 160 -1"

Test #2:

score: 0
Accepted
time: 49ms
memory: 11968kb

input:

400000
1 1
1 1000000000 1000000000000 1
1 1
2 1000000000 1 0
1 1
2 1 1000000000000 1
1 1
1 1 1000000000000 1
1 1
2 1000000000 1000000000000 0
1 1
2 1 1 0
1 1000000000000
2 1000000000 1 0
1 1000000000000
1 1 1 0
1 1000000000000
1 1 1 1
1 1000000000000
2 1000000000 1000000000000 0
1 1
1 1000000000 1 0...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 400000 numbers

Test #3:

score: 0
Accepted
time: 68ms
memory: 11972kb

input:

10000
4 542575683220
2 101300788 7308006925 1
1 604560531 257884671293 0
1 46911674 422781533607 0
2 10550533 771273976896 1
116 793781361888
1 819065134 15224463201 1
2 552573547 15992997563 1
2 424217 27032314690 0
2 70252887 41541882886 0
2 274093456 46129251985 0
1 458919850 46344406806 1
1 8416...

output:

-1
-1
-1
-1
-1
66660446969 904724933033
-1
-1
-1
-1
-1
-1
37226106549 311799565893
-1
-1
-1
-1
-1
-1
48301734080 375528816957
-1
-1
-1
459021288402 632610827258
-1
-1
-1
-1
-1
-1
-1
688320095661 898231263806
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
21800224424...

result:

ok 10846 numbers

Test #4:

score: 0
Accepted
time: 76ms
memory: 12164kb

input:

1000
41 699991536758
1 846433454 45030190307 1
2 882516075 48235731920 1
1 488580715 68600854082 1
2 467682948 92731902940 1
1 218024396 138543808852 1
2 124969525 150196554430 0
2 989301314 181283691649 1
2 752581868 202920989593 0
2 164838619 269703109427 0
1 696316428 295229433897 0
2 711333918 3...

output:

329739379675 908226682656
-1
-1
-1
-1
-1
424620801981 831021050071
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
6963797897 888755778656
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
568768655870 677350535270
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 1042 numbers

Test #5:

score: 0
Accepted
time: 104ms
memory: 8444kb

input:

100
5622 365182448552
2 639763453 293138584 0
1 150269480 461335412 1
1 215320018 935778069 1
2 455090474 986867198 1
2 137209887 1025838937 1
1 639542200 1323284104 0
2 975624632 1331236944 1
1 419729668 1535875032 0
1 754484749 1638561677 1
2 718600604 2047704086 0
2 793817561 2082808091 1
2 89416...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 100 numbers

Test #6:

score: 0
Accepted
time: 155ms
memory: 17060kb

input:

10
17647 497735816936
2 674642608 86555331 1
1 362561577 201254993 1
2 311798376 317505931 0
1 997152835 354905086 0
1 501042015 406191428 1
2 346791377 498440233 0
2 883536093 569248570 0
1 242082992 714310537 1
1 149897006 726750432 1
2 951017299 800159980 0
2 258554143 816615965 0
1 681430878 825...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 247ms
memory: 36828kb

input:

1
400000 263629556026
2 954826535 1576313 1
1 970048058 1644473 1
1 100070583 1779363 0
1 862973854 2602197 0
1 544583759 6163089 1
1 292939527 13244435 1
1 818324382 16877678 1
1 255969879 32429661 0
1 578761398 33091132 1
2 337038014 34601245 0
1 46604309 39135309 0
2 501363911 40833345 1
1 210491...

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

score: 0
Accepted
time: 449ms
memory: 70956kb

input:

1
399863 925298013757
2 100628989 1 0
2 879908544 1 0
2 835150000 1 0
2 965097317 1 0
2 806475166 1 0
2 883153545 1 0
2 537871549 1 0
2 666240466 1 0
2 772690810 1 0
2 468000116 1 0
2 57197741 1 0
2 752910244 1 0
2 34579873 1 0
2 764798890 1 0
2 385606621 1 0
2 359331506 1 0
2 280339733 1 0
2 485810...

output:

93600917303 93601131398

result:

ok 2 number(s): "93600917303 93601131398"

Test #9:

score: 0
Accepted
time: 439ms
memory: 70944kb

input:

1
399494 961261170252
1 500382911 1 0
1 343020544 1 0
1 754347645 1 0
1 333064084 1 0
1 478385269 1 0
1 622968098 1 0
1 980169601 1 0
1 352209103 1 0
1 402748538 1 0
1 218430474 1 0
1 288936411 1 0
1 5773706 1 0
1 698161932 1 0
1 366209929 1 0
1 73511871 1 0
1 725720796 1 0
1 888663191 1 0
1 3011404...

output:

93601000787 93601218921

result:

ok 2 number(s): "93601000787 93601218921"

Test #10:

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

input:

1
400000 663010
1 680238422 483214 0
1 680238422 521442 0
1 680238422 609593 0
1 680238422 1476058 0
1 680238422 2424603 0
1 680238422 2483379 0
1 680238422 2777054 0
1 680238422 3992033 0
1 680238422 4038346 0
1 680238422 4500144 0
1 680238422 4613302 0
1 680238422 4698260 0
1 680238422 4860707 0
1...

output:

-1

result:

ok 1 number(s): "-1"

Test #11:

score: 0
Accepted
time: 37ms
memory: 26004kb

input:

1
400000 79784
1 110051200 202567778970 0
1 110051200 202567778970 0
1 110051200 202567778970 0
1 110051200 202567778970 0
1 110051200 202567778970 0
1 110051200 202567778970 0
1 110051200 202567778970 0
1 110051200 202567778970 0
1 110051200 202567778970 0
1 110051200 202567778970 0
1 110051200 202...

output:

202567778970 879492417995

result:

ok 2 number(s): "202567778970 879492417995"

Test #12:

score: 0
Accepted
time: 134ms
memory: 44544kb

input:

1
400000 48790
1 554756625 480690 0
1 554756625 3230620 0
1 554756625 3409127 0
1 514075804 3753536 0
1 554756625 4724772 0
2 188054527 5311431 0
1 100903989 5807895 0
1 933163205 7291004 0
2 382472190 8139517 0
1 239315307 8310712 0
1 554756625 8348744 0
1 14438382 8939856 0
1 554756625 11989642 0
...

output:

13251717318 599133935039

result:

ok 2 number(s): "13251717318 599133935039"

Test #13:

score: 0
Accepted
time: 23ms
memory: 29016kb

input:

1
400000 255041
2 181766528 25787236213 0
2 181766528 25787236213 0
2 181766528 25787236213 0
2 181766528 25787236213 0
2 181766528 25787236213 0
2 181766528 25787236213 0
2 181766528 25787236213 0
2 181766528 25787236213 0
2 181766528 25787236213 0
2 181766528 25787236213 0
2 181766528 25787236213 ...

output:

306238410801 624516496355

result:

ok 2 number(s): "306238410801 624516496355"

Test #14:

score: 0
Accepted
time: 146ms
memory: 46696kb

input:

1
400000 952892
1 669079782 5249 0
1 669079782 1051034 0
1 669079782 1478798 0
1 643031526 2194715 0
1 669079782 2318113 0
2 195012273 3054972 0
2 608030266 3674227 0
1 927916867 3904831 0
1 669079782 4349111 0
2 214184786 6595409 0
1 669079782 6663358 0
2 403805672 6933063 0
1 669079782 7146955 0
2...

output:

13932447919 987373706861

result:

ok 2 number(s): "13932447919 987373706861"

Test #15:

score: 0
Accepted
time: 32ms
memory: 25892kb

input:

1
400000 445351
2 43725609 629636445 0
2 43725609 629636445 0
2 43725609 629636445 0
2 43725609 629636445 0
2 43725609 629636445 0
2 43725609 629636445 0
2 43725609 629636445 0
2 43725609 629636445 0
2 43725609 629636445 0
2 43725609 629636445 0
2 43725609 629636445 0
2 43725609 629636445 0
2 437256...

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0
Accepted
time: 182ms
memory: 44792kb

input:

1
400000 737917
2 104548428 355151 0
2 798447330 563764 0
2 807313778 726293 0
1 225967449 777825 0
1 76979820 830949 0
2 798447330 1204358 0
1 152843063 1242227 0
1 147816717 1604061 0
2 884732354 2045708 0
1 899307173 2280899 0
1 923713510 2447044 0
2 807313778 2651301 0
2 148086652 2704087 0
2 79...

output:

294972586721 744194775850

result:

ok 2 number(s): "294972586721 744194775850"

Test #17:

score: 0
Accepted
time: 42ms
memory: 29292kb

input:

1
400000 797979
1 698025121 76252326 0
1 698025121 76252326 0
1 698025121 76252326 0
1 698025121 76252326 0
1 698025121 76252326 0
1 698025121 76252326 0
1 698025121 76252326 0
1 698025121 76252326 0
1 698025121 76252326 0
1 698025121 76252326 0
1 698025121 76252326 0
1 698025121 76252326 0
1 698025...

output:

297321818946 857889105465

result:

ok 2 number(s): "297321818946 857889105465"

Test #18:

score: 0
Accepted
time: 270ms
memory: 49052kb

input:

1
400000 559759
1 334035078 470519 0
1 768140446 2967944 0
1 77040897 3088991 0
2 493261355 4283608 0
2 914055376 4561618 0
1 249929265 5223548 0
1 471764388 5364482 0
1 438202587 6820774 0
1 548072976 7173586 0
1 152064110 7904320 0
2 187798068 9277616 0
2 554380228 11571775 0
2 999624048 11848525 ...

output:

368607061812 459867556579

result:

ok 2 number(s): "368607061812 459867556579"

Test #19:

score: 0
Accepted
time: 82ms
memory: 34756kb

input:

1
400000 923129
1 830682125 6777784 0
1 830682125 6777784 0
1 830682125 6777784 0
1 830682125 6777784 1
1 830682125 6777784 0
1 830682125 6777784 0
1 830682125 6777784 0
2 502376403 98306211 0
2 502376403 98306211 0
2 502376403 98306211 0
2 502376403 98306211 0
2 502376403 98306211 0
2 502376403 983...

output:

603264713406 904051411073

result:

ok 2 number(s): "603264713406 904051411073"

Test #20:

score: 0
Accepted
time: 121ms
memory: 11972kb

input:

10000
34 713414155711
1 353899840 4470478880 1
1 101300788 14617874162 1
2 224463201 46129251985 1
2 997067155 53850132914 1
1 493411629 67237771644 1
2 60685412 153612550178 1
2 932182989 159471048139 1
2 821881991 174028196456 1
2 887385900 188331357182 1
2 819065134 200111294061 1
2 348545253 247...

output:

483871970490 840598269617
196200037892 970964066001
283567194848 914830957817
-1
-1
224079150450 800412473197
100330184885 227585151128
50506210564 783882723066
406628103960 924434625801
634770465011 738356832148
16323343084 723566375795
28913275304 938587397050
-1
461193028837 931629993981
36470471...

result:

ok 18515 numbers

Test #21:

score: 0
Accepted
time: 164ms
memory: 12252kb

input:

1000
60 171285665612
1 202084572 21122606424 1
2 658066585 35408059059 1
1 23311972 51059588296 1
1 555006790 53867325184 1
2 668895851 61404100899 1
2 439334198 66467682948 1
2 814813731 75505419882 1
2 563694648 84052137524 1
1 863531125 84160720592 1
2 666879230 92731902940 1
1 310726910 12688787...

output:

200468370512 983989301314
105910501928 853497904904
928492782007 939126373321
342619682920 456502006066
282459092744 713342359655
99203627100 110822178667
496813497898 828241040007
5149945202 998323717204
20989066921 948454205300
353986139415 989439227450
134191973984 722450971884
64821218433 932293...

result:

ok 1942 numbers

Test #22:

score: 0
Accepted
time: 214ms
memory: 19772kb

input:

100
302 495480207413
1 157557196 5191700656 1
2 688131848 7822346081 1
2 302959585 11342249961 1
2 667487485 12602857386 1
1 981368818 14235797064 1
2 862638974 15778895657 1
2 938801239 16033062185 1
2 141565804 18783237506 1
2 600109241 21882439145 1
1 866713826 23983150467 1
2 17855262 2555711801...

output:

12878839367 465356894994
98670299607 984006430918
659460612429 921298289091
261717617158 758562225078
16656906317 946242259897
604865303455 742610447485
65635714807 979156099520
414255260549 900331635889
86571338038 510051964019
302298934987 885584590000
15514653060 928519135170
11536475812 99954734...

result:

ok 197 numbers

Test #23:

score: 0
Accepted
time: 313ms
memory: 31368kb

input:

10
69720 312974804124
1 375110834 3284756 1
2 958035607 5372989 1
1 96816917 5896324 1
1 659349114 23601583 1
1 123026525 45334114 1
2 810136368 59250875 1
2 382704738 59429789 1
1 397855561 69769833 1
2 194473720 85533928 1
1 41349414 87337444 1
1 854195287 89285949 1
2 208588652 102226384 1
2 8322...

output:

192359142508 690359228247
4301019212 770771226671
59321270708 972659014596
34895107242 342872704017
43369717825 828295749790
281202583338 607302423053
105982895679 805855161263
12072175115 993484291384
114227155230 666678426833
136839246084 981181564986

result:

ok 20 numbers

Test #24:

score: 0
Accepted
time: 507ms
memory: 71520kb

input:

1
400000 862246722332
1 879284128 1644473 1
1 566310427 2602197 1
1 305759998 3635844 1
2 306032716 11995694 1
2 389513871 14509476 1
2 761692038 14593427 1
2 924522024 17673793 1
1 604735028 18750462 1
2 312343123 19169330 1
1 37783135 19583722 1
2 765576144 19935364 1
1 508498315 23251498 1
2 3123...

output:

511340089351 555367600772

result:

ok 2 number(s): "511340089351 555367600772"

Test #25:

score: 0
Accepted
time: 439ms
memory: 69552kb

input:

1
400000 601546500618
1 193617644 437488 1
1 687635851 1161220 1
1 867854270 3644275 1
2 75321946 7668994 1
2 19512874 8264014 1
2 2373384 11375302 1
2 167691473 17921764 1
1 837478720 23661825 1
1 319362132 27535622 1
2 9492126 28282384 1
2 21937131 28442718 1
1 284421469 28539626 1
1 313762592 307...

output:

212927310768 944532983806

result:

ok 2 number(s): "212927310768 944532983806"

Test #26:

score: 0
Accepted
time: 105ms
memory: 12040kb

input:

10000
59 10000000000
2 38224116 294735 0
1 791184194 294735 1
2 38224116 1963991 1
1 46743924 2052699 1
1 555377382 3945603 1
2 686459062 3952976 1
2 905596132 7512134 1
2 420873888 8587106 1
1 586803310 8596700 1
1 755231195 12584511 1
1 403524468 17231015 1
1 460174100 23414884 1
2 115239866 25206...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 13652 numbers

Test #27:

score: 0
Accepted
time: 149ms
memory: 12240kb

input:

1000
99 10000000000
2 307832277 78148 0
2 307832277 78148 1
1 275518058 2292869 1
2 318752188 3421425 1
1 538132005 4313972 1
2 559436916 4729882 1
2 97509167 4815124 1
2 154178279 4851744 1
2 567062651 6312029 1
2 665106524 7115329 1
2 715927148 8744720 1
1 502131755 9331956 1
2 809734156 9420053 1...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 1468 numbers

Test #28:

score: 0
Accepted
time: 214ms
memory: 15780kb

input:

100
10051 10000000000
2 139050006 1151 0
2 139050006 1151 1
1 500313852 6700 1
2 681995605 9186 1
1 270810606 22090 1
1 995827512 24954 1
1 53631098 30759 1
1 399843074 46446 1
2 126028509 48532 1
1 981492639 53805 1
2 702955098 123192 1
1 795346040 129998 1
2 556795597 151390 1
1 989719151 160084 1...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
182168532 694021729
-1
-1
-1
-1
577259203 783733321
-1
-1
-1
671704640 925928203
-1
-1
-1
-1
-1
138312166 436590105
-1
130000444 166930180
1796852385 5828587855
3700769434 7831971589
5341012067 6770347121
-1
924292593 5310349577
11307...

result:

ok 154 numbers

Test #29:

score: 0
Accepted
time: 320ms
memory: 37160kb

input:

10
128435 10000000000
2 650210546 297 0
2 650210546 297 1
1 614257067 1396 1
2 303092138 3047 1
1 571581225 3700 1
2 385229129 4100 1
1 445435100 4835 1
2 193655129 6197 1
2 153784571 7701 1
1 104200814 10218 1
1 60272333 10546 1
1 633189238 11303 1
1 100743505 11632 1
1 402614614 11726 1
2 6587875 ...

output:

-1
-1
-1
-1
5027602745 7828469284
809575451 2243952975
50008876934 92680594103
68404371711 98198887855
599544816032 676768101584
32564552152 866063397702

result:

ok 16 numbers

Test #30:

score: 0
Accepted
time: 412ms
memory: 71480kb

input:

1
399999 10000000000
2 233850926 90 0
1 748456332 90 1
1 213487336 626 1
1 157311336 716 1
1 28947387 765 1
1 424478786 1436 1
1 548164753 1638 1
1 431903000 1949 1
2 233850926 2028 1
2 716019297 2086 1
2 275417128 2176 1
2 289866313 2231 1
2 275427198 2822 1
2 749995741 2921 1
1 874030515 3547 1
2 ...

output:

-1

result:

ok 1 number(s): "-1"

Test #31:

score: 0
Accepted
time: 466ms
memory: 71592kb

input:

1
399999 10000000000
1 326385488 311 0
1 326385488 311 1
1 203877106 1099 1
2 644432124 1199 1
2 127852006 1290 1
2 407011871 1404 1
1 167030010 1854 1
1 704974376 2001 1
2 176461067 2510 1
2 528064718 2688 1
2 558130105 2947 1
2 472257639 3212 1
1 17497002 3607 1
1 887225470 3609 1
1 885238663 3997...

output:

47241340 63768254

result:

ok 2 number(s): "47241340 63768254"

Test #32:

score: 0
Accepted
time: 438ms
memory: 69500kb

input:

1
399999 10000000000
2 720746168 2538 0
1 389889266 2538 1
1 846649225 3346 1
2 720746168 6867 1
2 220578380 8319 1
2 478006698 14785 1
1 543403305 15269 1
1 994117268 17197 1
1 244609566 17573 1
1 186393243 18023 1
1 429534436 19900 1
1 831875453 21942 1
2 708904325 22934 1
2 674347985 25188 1
1 89...

output:

63929246 848919318

result:

ok 2 number(s): "63929246 848919318"

Test #33:

score: 0
Accepted
time: 448ms
memory: 71548kb

input:

1
399999 10000000000
1 708135129 3777 0
1 708135129 3777 1
2 378842907 12099 1
2 491334572 15760 1
2 57000817 22432 1
2 107356454 24206 1
1 355006013 25808 1
1 215578462 26957 1
1 915491561 27307 1
2 955971633 39399 1
2 609588029 44169 1
2 842497351 48865 1
1 617427596 53607 1
2 398484603 54969 1
2 ...

output:

27037798 925795917

result:

ok 2 number(s): "27037798 925795917"

Test #34:

score: 0
Accepted
time: 454ms
memory: 71524kb

input:

1
399999 10000000000
2 85635799 55054 0
2 85635799 55054 1
1 280335848 174979 1
2 939318300 209001 1
2 894465429 284645 1
2 618497444 297291 1
2 965916461 360005 1
1 974758958 400989 1
1 764253644 422154 1
2 15313245 481707 1
2 663242137 493111 1
1 798251629 520714 1
1 578532763 538498 1
2 468635252...

output:

996300115 8421496745

result:

ok 2 number(s): "996300115 8421496745"

Test #35:

score: 0
Accepted
time: 480ms
memory: 71544kb

input:

1
399999 10000000000
1 419779110 42873 0
2 809879504 42873 1
2 969885028 63945 1
1 419779110 78559 1
2 833465970 114507 1
1 575954552 137275 1
2 845350982 144299 1
1 829415866 177492 1
2 377975311 191331 1
2 543827092 388125 1
2 954840061 429840 1
1 234193563 430657 1
2 814992278 519061 1
2 13492113...

output:

3348662196 5187741015

result:

ok 2 number(s): "3348662196 5187741015"

Test #36:

score: 0
Accepted
time: 445ms
memory: 69560kb

input:

1
399999 10000000000
2 53438133 376125 0
2 53438133 376125 1
2 987743109 395850 1
1 166707936 441017 1
2 740702438 626572 1
2 254475979 650308 1
2 327881470 975326 1
1 519757004 1146648 1
1 745882219 1449930 1
1 704933732 1504462 1
1 567410879 1660559 1
1 501447393 2155145 1
1 217253545 2205303 1
2 ...

output:

75248596220 96080897908

result:

ok 2 number(s): "75248596220 96080897908"

Test #37:

score: 0
Accepted
time: 451ms
memory: 69344kb

input:

1
399999 10000000000
1 490359113 409073 0
2 635603234 409073 1
1 490359113 582604 1
1 466100352 1806496 1
1 851462909 2072668 1
2 835324462 2096985 1
1 306968106 2569687 1
2 843905600 2624494 1
1 421262349 2841982 1
2 566061630 3227185 1
1 840367098 3398146 1
1 755106699 3440275 1
1 893965367 398535...

output:

-1

result:

ok 1 number(s): "-1"

Test #38:

score: 0
Accepted
time: 462ms
memory: 69500kb

input:

1
399999 10000000000
2 108713408 355367 0
1 495440048 355367 1
2 108713408 5246476 1
1 829460048 18527254 1
2 643329162 19258328 1
2 889222716 22102287 1
2 408057726 26361813 1
2 793626956 26469500 1
2 138076520 29441704 1
1 91238764 31551010 1
2 871893174 31820730 1
1 668770819 34779933 1
1 8155239...

output:

326517728008 374248053587

result:

ok 2 number(s): "326517728008 374248053587"

Test #39:

score: 0
Accepted
time: 437ms
memory: 71592kb

input:

1
399999 10000000000
1 107735064 1466866 0
2 435376868 1466866 1
1 107735064 4168250 1
1 514024463 6140405 1
2 743983631 11245466 1
1 806314530 15082970 1
1 785572414 15407736 1
1 210419929 17442417 1
2 614548459 17450482 1
1 82717421 17736378 1
2 747895352 19709129 1
2 512995307 20474608 1
1 917777...

output:

24033093497 889551871011

result:

ok 2 number(s): "24033093497 889551871011"

Extra Test:

score: 0
Extra Test Passed