QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#896371#10006. Good Trianglecmk666AC ✓187ms29528kbC++2311.3kb2025-02-13 10:18:012025-02-13 10:18:03

Judging History

This is the latest submission verdict.

  • [2025-02-13 10:18:03]
  • Judged
  • Verdict: AC
  • Time: 187ms
  • Memory: 29528kb
  • [2025-02-13 10:18:01]
  • Submitted

answer

/*  _              _     _                                             _       __      __      __   
   / \     _   _  | |_  | |__     ___    _ __   _    ___   _ __ ___   | | __  / /_    / /_    / /_  
  / _ \   | | | | | __| | '_ \   / _ \  | '__| (_)  / __| | '_ ` _ \  | |/ / | '_ \  | '_ \  | '_ \ 
 / ___ \  | |_| | | |_  | | | | | (_) | | |     _  | (__  | | | | | | |   <  | (_) | | (_) | | (_) |
/_/   \_\  \__,_|  \__| |_| |_|  \___/  |_|    (_)  \___| |_| |_| |_| |_|\_\  \___/   \___/   \___/ 
[Created Time:       2025-02-13 10:08:49]
[Last Modified Time: 2025-02-13 10:17:53] */
#ifdef LOCAL
#include<bits/stdc++.h>
#include"debug.h"
#else
#pragma GCC optimize("Ofast", "unroll-loops")
#include<bits/stdc++.h>
#define D(...) ((void)0)
#endif
using namespace std; using ll = long long;
#define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ )
#define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- )
namespace FastIO
{
#define USE_FastIO
// ------------------------------
// #define DISABLE_MMAP
// ------------------------------
#if ( defined(LOCAL) || defined(_WIN32) ) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifdef LOCAL
	inline void _chk_i() {}
	inline char _gc_nochk() { return getchar(); }
	inline char _gc() { return getchar(); }
	inline void _chk_o() {}
	inline void _pc_nochk(char c) { putchar(c); }
	inline void _pc(char c) { putchar(c); }
	template < int n > inline void _pnc_nochk(const char *c) { for ( int i = 0 ; i < n ; i++ ) putchar(c[i]); }
#else
#ifdef DISABLE_MMAP
	inline constexpr int _READ_SIZE = 1 << 18; inline static char _read_buffer[_READ_SIZE + 40], *_read_ptr = nullptr, *_read_ptr_end = nullptr; static inline bool _eof = false;
	inline void _chk_i() { if ( __builtin_expect(!_eof, true) && __builtin_expect(_read_ptr_end - _read_ptr < 40, false) ) { int sz = _read_ptr_end - _read_ptr; if ( sz ) memcpy(_read_buffer, _read_ptr, sz); char *beg = _read_buffer + sz; _read_ptr = _read_buffer, _read_ptr_end = beg + fread(beg, 1, _READ_SIZE, stdin); if ( __builtin_expect(_read_ptr_end != beg + _READ_SIZE, false) ) _eof = true, *_read_ptr_end = EOF; } }
	inline char _gc_nochk() { return __builtin_expect(_eof && _read_ptr == _read_ptr_end, false) ? EOF : *_read_ptr++; }
	inline char _gc() { _chk_i(); return _gc_nochk(); }
#else
#include<sys/mman.h>
#include<sys/stat.h>
	inline static char *_read_ptr = (char *)mmap(nullptr, [] { struct stat s; return fstat(0, &s), s.st_size; } (), 1, 2, 0, 0);
	inline void _chk_i() {}
	inline char _gc_nochk() { return *_read_ptr++; }
	inline char _gc() { return *_read_ptr++; }
#endif
	inline constexpr int _WRITE_SIZE = 1 << 18; inline static char _write_buffer[_WRITE_SIZE + 40], *_write_ptr = _write_buffer;
	inline void _chk_o() { if ( __builtin_expect(_write_ptr - _write_buffer > _WRITE_SIZE, false) ) fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout), _write_ptr = _write_buffer; }
	inline void _pc_nochk(char c) { *_write_ptr++ = c; }
	inline void _pc(char c) { *_write_ptr++ = c, _chk_o(); }
	template < int n > inline void _pnc_nochk(const char *c) { memcpy(_write_ptr, c, n), _write_ptr += n; }
	inline struct _auto_flush { inline ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); } } _auto_flush;
#endif
#define println println_ // don't use C++23 std::println
	template < class T > inline constexpr bool _is_signed = numeric_limits < T >::is_signed;
	template < class T > inline constexpr bool _is_unsigned = numeric_limits < T >::is_integer && !_is_signed < T >;
#if __SIZEOF_LONG__ == 64
	template <> inline constexpr bool _is_signed < __int128 > = true;
	template <> inline constexpr bool _is_unsigned < __uint128_t > = true;
#endif
	inline bool _isgraph(char c) { return c >= 33; }
	inline bool _isdigit(char c) { return 48 <= c && c <= 57; } // or faster, remove c <= 57
	constexpr struct _table {
#ifndef LOCAL
	int i[65536];
#endif
	char o[40000]; constexpr _table() :
#ifndef LOCAL
	i{},
#endif
	o{} {
#ifndef LOCAL
	for ( int x = 0 ; x < 65536 ; x++ ) i[x] = -1; for ( int x = 0 ; x <= 9 ; x++ ) for ( int y = 0 ; y <= 9 ; y++ ) i[x + y * 256 + 12336] = x * 10 + y;
#endif
	for ( int x = 0 ; x < 10000 ; x++ ) for ( int y = 3, z = x ; ~y ; y-- ) o[x * 4 + y] = z % 10 + 48, z /= 10; } } _table;
	template < class T, int digit > inline constexpr T _pw10 = 10 * _pw10 < T, digit - 1 >;
	template < class T > inline constexpr T _pw10 < T, 0 > = 1;
	inline void read(char &c) { do c = _gc(); while ( !_isgraph(c) ); }
	inline void read_cstr(char *s) { char c = _gc(); while ( !_isgraph(c) ) c = _gc(); while ( _isgraph(c) ) *s++ = c, c = _gc(); *s = 0; }
	inline void read(string &s) { char c = _gc(); s.clear(); while ( !_isgraph(c) ) c = _gc(); while ( _isgraph(c) ) s.push_back(c), c = _gc(); }
	template < class T, bool neg >
#ifndef LOCAL
	__attribute__((no_sanitize("undefined")))
#endif
	inline void _read_int_suf(T &x) { _chk_i(); char c; while
#ifndef LOCAL
	( ~_table.i[*reinterpret_cast < unsigned short *& >(_read_ptr)] ) if constexpr ( neg ) x = x * 100 - _table.i[*reinterpret_cast < unsigned short *& >(_read_ptr)++]; else x = x * 100 + _table.i[*reinterpret_cast < unsigned short *& >(_read_ptr)++]; if
#endif
	( _isdigit(c = _gc_nochk()) ) if constexpr ( neg ) x = x * 10 - ( c & 15 ); else x = x * 10 + ( c & 15 ); }
	template < class T, enable_if_t < _is_signed < T >, int > = 0 > inline void read(T &x) { char c; while ( !_isdigit(c = _gc()) ) if ( c == 45 ) { _read_int_suf < T, true >(x = -( _gc_nochk() & 15 )); return; } _read_int_suf < T, false >(x = c & 15); }
	template < class T, enable_if_t < _is_unsigned < T >, int > = 0 > inline void read(T &x) { char c; while ( !_isdigit(c = _gc()) ); _read_int_suf < T, false >(x = c & 15); }
	inline void write(bool x) { _pc(x | 48); }
	inline void write(char c) { _pc(c); }
	inline void write_cstr(const char *s) { while ( *s ) _pc(*s++); }
	inline void write(const string &s) { for ( char c : s ) _pc(c); }
	template < class T, bool neg, int digit > inline void _write_int_suf(T x) { if constexpr ( digit == 4 ) _pnc_nochk < 4 >(_table.o + ( neg ? -x : x ) * 4); else _write_int_suf < T, neg, digit / 2 >(x / _pw10 < T, digit / 2 >), _write_int_suf < T, neg, digit / 2 >(x % _pw10 < T, digit / 2 >); }
	template < class T, bool neg, int digit > inline void _write_int_pre(T x) { if constexpr ( digit <= 4 ) if ( digit >= 3 && ( neg ? x <= -100 : x >= 100 ) ) if ( digit >= 4 && ( neg ? x <= -1000 : x >= 1000 ) ) _pnc_nochk < 4 >(_table.o + ( neg ? -x : x ) * 4); else _pnc_nochk < 3 >(_table.o + ( neg ? -x : x ) * 4 + 1); else if ( digit >= 2 && ( neg ? x <= -10 : x >= 10 ) ) _pnc_nochk < 2 >(_table.o + ( neg ? -x : x ) * 4 + 2); else _pc_nochk(( neg ? -x : x ) | 48); else { constexpr int cur = 1 << __lg(digit - 1); if ( neg ? x <= -_pw10 < T, cur > : x >= _pw10 < T, cur > ) _write_int_pre < T, neg, digit - cur >(x / _pw10 < T, cur >), _write_int_suf < T, neg, cur >(x % _pw10 < T, cur >); else _write_int_pre < T, neg, cur >(x); } }
	template < class T, enable_if_t < _is_signed < T >, int > = 0 > inline void write(T x) { if ( x >= 0 ) _write_int_pre < T, false, numeric_limits < T >::digits10 + 1 >(x); else _pc_nochk(45), _write_int_pre < T, true, numeric_limits < T >::digits10 + 1 >(x); _chk_o(); }
	template < class T, enable_if_t < _is_unsigned < T >, int > = 0 > inline void write(T x) { _write_int_pre < T, false, numeric_limits < T >::digits10 + 1 >(x), _chk_o(); }
	template < size_t N, class ...T > inline void _read_tuple(tuple < T... > &x) { read(get < N >(x)); if constexpr ( N + 1 != sizeof...(T) ) _read_tuple < N + 1, T... >(x); }
	template < size_t N, class ...T > inline void _write_tuple(const tuple < T... > &x) { write(get < N >(x)); if constexpr ( N + 1 != sizeof...(T) ) _pc(32), _write_tuple < N + 1, T... >(x); }
	template < class ...T > inline void read(tuple < T... > &x) { _read_tuple < 0, T... >(x); }
	template < class ...T > inline void write(const tuple < T... > &x) { _write_tuple < 0, T... >(x); }
	template < class T1, class T2 > inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); }
	template < class T1, class T2 > inline void write(const pair < T1, T2 > &x) { write(x.first), _pc(32), write(x.second); }
	template < class T > inline auto read(T &x) -> decltype(x.read(), void()) { x.read(); }
	template < class T > inline auto write(const T &x) -> decltype(x.write(), void()) { x.write(); }
	template < class T1, class ...T2 > inline void read(T1 &x, T2 &...y) { read(x), read(y...); }
	template < class ...T > inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
	template < class T1, class ...T2 > inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); }
	template < class ...T > inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
	template < class T > inline void print(const T &x) { write(x); }
	inline void print_cstr(const char *x) { write_cstr(x); }
	template < class T1, class ...T2 > inline void print(const T1 &x, const T2 &...y) { write(x), _pc(32), print(y...); }
	template < class ...T > inline void print_cstr(const char *x, const T *...y) { write_cstr(x), _pc(32), print_cstr(y...); }
	inline void println() { _pc(10); }
	inline void println_cstr() { _pc(10); }
	template < class ...T > inline void println(const T &...x) { print(x...), _pc(10); }
	template < class ...T > inline void println_cstr(const T *...x) { print_cstr(x...), _pc(10); }
}	using FastIO::read, FastIO::read_cstr, FastIO::write, FastIO::write_cstr, FastIO::println, FastIO::println_cstr;
struct
{
	using T = int; T v[500009]; int l;
	inline void clear() { l = 0; }
	inline void push(T x) { v[++l] = x; }
	inline void build() { sort(v + 1, v + l + 1), l = unique(v + 1, v + l + 1) - v - 1; }
	inline int pre(T x)const { return upper_bound(v + 1, v + l + 1, x) - v - 1; }
	inline int nxt(T x)const { return lower_bound(v + 1, v + l + 1, x) - v; }
	inline int id(T x)const { return nxt(x); }
	inline int len()const { return l; }
	inline T val(int x)const { return v[x]; }
}	d;
namespace BIT
{
	using T = int; int n; T c[500009];
	inline void init(int x) { n = x, fill(c + 1, c + n + 1, 0); }
	inline void add(int x, T y) { for ( ; x <= n ; x += x & -x ) c[x] += y; }
	inline T qry(int x) { T y = 0; for ( ; x ; x ^= x & -x ) y += c[x]; return y; }
	inline T qry(int x, int y) { return qry(y) - qry(x - 1); }
}
int n, x, y, o, f[500009], ff[500009], g[500009], gg[500009]; pair < int, int > a[500009]; ll ans;
int main()
{
	read(n), ans = n * ( n - 1ll ) * ( n - 2 ) / 6;
	For(i, 1, n) read(x, y), a[i] = pair(x - y, x + y), d.push(a[i].second);
	d.build(); For(i, 1, n) a[i].second = d.id(a[i].second);
	sort(a + 1, a + n + 1), BIT::init(d.len());
	for ( int l = 1, r ; l <= n ; l = r + 1 )
	{
		for ( r = l ; r < n && a[l].first == a[r + 1].first ; r++ );
		For(i, l, r) f[i] = BIT::qry(a[i].second - 1), ff[i] = BIT::qry(a[i].second + 1, d.len());
		For(i, l, r) BIT::add(a[i].second, 1);
	}
	BIT::init(d.len());
	for ( int l, r = n ; r >= 1 ; r = l - 1 )
	{
		for ( l = r ; l > 1 && a[r].first == a[l - 1].first ; l-- );
		For(i, l, r) g[i] = BIT::qry(a[i].second - 1), gg[i] = BIT::qry(a[i].second + 1, d.len());
		For(i, l, r) BIT::add(a[i].second, 1);
	}
	For(i, 1, n) ans -= (ll)f[i] * gg[i] + (ll)ff[i] * g[i];
	return println(ans), 0;
}
// 想上GM捏 想上GM捏 想上GM捏 想上GM捏 想上GM捏
// 伊娜可爱捏 伊娜贴贴捏

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 16080kb

input:

5
1 -1
1 5
5 7
1 3
4 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

10
-2 -1
-2 2
-1 -2
-1 -1
-1 1
0 1
1 -1
1 2
2 -1
2 1

output:

108

result:

ok 1 number(s): "108"

Test #3:

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

input:

8
-5353885 177168259
393803106 -221988732
517220368 -345405994
143143400 28670974
-179553118 351367492
447166616 -275352242
-72145562 243959936
-274698525 446512899

output:

56

result:

ok 1 number(s): "56"

Test #4:

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

input:

8
-324947127 116858935
372954148 -81124978
54845173 -262933365
122995467 -331083659
-350010483 641839653
-599969164 391880972
-74988446 366817616
-73250266 365079436

output:

56

result:

ok 1 number(s): "56"

Test #5:

score: 0
Accepted
time: 1ms
memory: 16080kb

input:

10
157433098 -150486510
741495015 -58558849
860039937 59986073
613972809 306053201
403500226 -396553638
68842013 -239077595
314909141 -485144723
-24746679 -332666287
221320449 -578733415
495427887 187508279

output:

120

result:

ok 1 number(s): "120"

Test #6:

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

input:

9
179264487 -544344907
139756831 -583852563
481689324 -241920070
223597013 -500012381
828224017 104614623
14865396 -708743998
89252586 -634356808
475703232 -247906162
301875222 -421734172

output:

84

result:

ok 1 number(s): "84"

Test #7:

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

input:

10
-623065093 198755267
-368090840 -393092046
225795796 409211766
-93406399 728413961
372178992 555594962
52976797 874797157
-303862898 -120446928
-472299428 -288883458
-791501623 30318737
476387580 451386374

output:

114

result:

ok 1 number(s): "114"

Test #8:

score: 0
Accepted
time: 1ms
memory: 14032kb

input:

8
-436280563 40679439
68302509 -89073311
-52148970 471776818
589381280 336967420
34530786 385097062
-248865402 228094600
-333757066 143202936
-119112652 -276488472

output:

49

result:

ok 1 number(s): "49"

Test #9:

score: 0
Accepted
time: 1ms
memory: 16080kb

input:

10
-477236362 165824920
188776620 -500188062
-8340601 577345567
662040674 -93035708
-159868135 425818033
78314899 664001067
497779358 -191185324
-123585922 462100246
-60356350 802672316
184430545 648794743

output:

106

result:

ok 1 number(s): "106"

Test #10:

score: 0
Accepted
time: 120ms
memory: 29360kb

input:

499998
-12023827 330263227
-664373810 24735206
305768212 -67930490
368765325 213424915
33206371 919185805
-647540955 191952141
355341003 -524613427
539454004 145694368
-404535204 559105834
-740702365 168088895
-149191340 -73936930
195872405 -752246739
34365000 -408325744
576078603 -102167279
4304638...

output:

13931045633752587

result:

ok 1 number(s): "13931045633752587"

Test #11:

score: 0
Accepted
time: 140ms
memory: 29396kb

input:

500000
517325606 -199260210
115196805 -56572125
281056762 -433461176
-161659966 498283130
-391924031 464800253
766549774 174283342
525457342 344241686
-246618483 84917847
39189914 -322670742
262995692 696558940
-560096113 -5709187
368102396 553155380
261954520 -636827658
-12851107 -877034845
5250120...

output:

13895596871211648

result:

ok 1 number(s): "13895596871211648"

Test #12:

score: 0
Accepted
time: 178ms
memory: 29524kb

input:

500000
-133502744 -90507140
646933552 219286468
-373613434 -504884618
-343025188 -595434664
-8003492 -638812988
-685998945 -46092109
341647783 -584356157
91652618 907982040
17995628 39810530
498261616 476740824
-852365722 -106180910
-294452584 -467043076
-244926348 -342666982
-532774098 -96117142
-8...

output:

13891775451269110

result:

ok 1 number(s): "13891775451269110"

Test #13:

score: 0
Accepted
time: 181ms
memory: 29476kb

input:

499999
114506099 -246676185
-459593763 388129679
297744224 -342595828
-817717759 -100918027
495509096 -412787144
245090361 -611617455
105906132 -306778712
-253921556 -217999540
593744189 -394716307
56313297 70718451
-647640628 -149060026
-658297766 54530742
343875812 -414202580
-559349589 -68020201
...

output:

13885578636476121

result:

ok 1 number(s): "13885578636476121"

Test #14:

score: 0
Accepted
time: 185ms
memory: 29528kb

input:

499998
125744151 -450232279
-600722706 356800788
-517315437 302443511
130795521 234400367
555475526 236342596
-190901050 586825122
-227691638 -139374086
517388093 1592767
-664085466 -191643176
390306640 593384378
280422726 219378472
-322113133 191283935
726764465 212908491
-754519643 244082977
-2449...

output:

13891247749090827

result:

ok 1 number(s): "13891247749090827"

Test #15:

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

input:

10
-2 -2
-1 -3
-1 -1
-2 -3
-1 1
-2 1
-1 -2
-2 0
-2 -1
-1 0

output:

82

result:

ok 1 number(s): "82"

Test #16:

score: 0
Accepted
time: 1ms
memory: 14232kb

input:

9999
50 3
60 -9
-10 19
16 29
54 12
-36 85
27 10
12 59
-32 -1
20 -4
42 1
55 52
27 84
-22 61
53 -5
52 84
9 31
-18 22
51 47
13 42
13 90
54 84
-6 24
55 50
-29 16
27 -6
5 63
-11 58
-16 -1
45 44
17 55
-10 87
16 45
-13 77
34 10
55 77
59 29
-23 0
-10 2
59 75
9 23
-36 17
13 41
52 90
11 74
-25 60
-21 21
-25 7...

output:

121482420921

result:

ok 1 number(s): "121482420921"

Test #17:

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

input:

9998
-66 23
-43 -3
-63 17
-76 29
-17 11
44 28
21 -3
-92 -16
-21 13
71 -15
-62 21
11 13
-84 -5
-4 10
-105 -15
-46 -6
84 26
-51 -9
-103 10
-4 -12
-56 2
-43 27
-47 -6
49 -7
70 -12
17 1
-95 10
-93 -14
41 6
-108 6
-89 -18
62 5
42 -14
-59 28
67 23
21 13
76 3
-64 3
-3 4
-86 17
74 -8
73 -10
-24 18
46 -6
63 ...

output:

66983215340

result:

ok 1 number(s): "66983215340"

Test #18:

score: 0
Accepted
time: 158ms
memory: 28504kb

input:

499999
-691836 661884688
-2436 505317808
-1161096 -730434632
-1171594 -235603628
-1301917 -440281561
-55737 878513579
-1020033 -302111631
-612334 -862337634
-27759 525559643
-1109391 22891985
-685524 151691948
-110298 487560846
-1075735 -523361837
-1259798 -264279164
-884836 -60690392
-1249007 -2237...

output:

0

result:

ok 1 number(s): "0"

Test #19:

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

input:

9
-174859413 67479603
-165982926 -750447504
-64675724 -649140302
-409704313 -506726117
-579384723 -337045707
373683278 616022294
-308397111 -405418915
238542384 -345922194
543363688 446341884

output:

81

result:

ok 1 number(s): "81"

Test #20:

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

input:

9
-30505280 -96692436
-352066529 224868813
18703576 395807198
-81212284 495723058
133498126 510601748
-628575696 -51640354
355143515 288956359
356225648 58285126
646938732 109317308

output:

68

result:

ok 1 number(s): "68"

Test #21:

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

input:

8
-6252574 926145266
-3251628 292749178
793627698 -177205438
474299239 348561843
624436646 -334939096
553235754 427498358
24168136 956565976
263430138 559430944

output:

48

result:

ok 1 number(s): "48"

Test #22:

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

input:

500000
-25426352 -523741786
-524917184 -27267878
129252045 111623837
-56741756 -100069842
-124854449 871500355
-166033088 700908754
-121420344 537816864
576876704 -54525192
683761081 27492447
244658809 -687059053
-179696382 -182849328
747616040 -970134
20122152 -861423358
-112425060 498441880
-21407...

output:

13931932690968428

result:

ok 1 number(s): "13931932690968428"

Test #23:

score: 0
Accepted
time: 137ms
memory: 29396kb

input:

499998
-361093233 280354011
213909100 66923890
23012067 -177712969
852739484 51954774
-489026011 -213002691
-649547359 295397785
-610097861 -315086587
224760452 623080324
515103844 -401155764
-708615480 -114987500
-19640920 347384418
-596944985 139194989
-835517532 -121723026
841202967 -126650761
-3...

output:

13893628573079030

result:

ok 1 number(s): "13893628573079030"

Test #24:

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

input:

499998
66027824 -607714988
53807202 -316330396
282896796 -393807218
17013651 -366155989
9063681 -273699961
-161526210 -183229200
-145519626 632934318
677452438 -6442652
375483956 367699366
402180648 -123017642
-521027263 68458745
136684004 790281014
-208899564 350981464
-185021085 558396449
44858009...

output:

13886867726622665

result:

ok 1 number(s): "13886867726622665"

Test #25:

score: 0
Accepted
time: 183ms
memory: 29336kb

input:

499998
261393864 703423492
675210021 -242296107
-363522149 -186495859
-524364828 -382482540
644352547 -76231155
-229199368 -392581852
-489412518 -133309098
-43716180 434314262
905404565 -68028673
-242434008 328258572
-330784787 435947511
-322563656 138145322
-620240082 120873868
433259558 290481336
...

output:

13893139257743113

result:

ok 1 number(s): "13893139257743113"

Test #26:

score: 0
Accepted
time: 187ms
memory: 29356kb

input:

499999
730787802 237525976
43914682 -949957808
84930346 654460864
-194218476 118506516
246511246 -232489584
160234390 543207570
-319654366 366871836
-233340343 593495633
495673669 -57650069
-572811208 161673736
544562411 -334344335
-104534508 -437879466
787604741 11330803
618707496 -348702306
-62400...

output:

13890046508710202

result:

ok 1 number(s): "13890046508710202"

Test #27:

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

input:

8
-2 -3
-1 -3
-2 0
-2 -4
-1 0
-2 -1
-1 -1
-2 -2

output:

38

result:

ok 1 number(s): "38"

Test #28:

score: 0
Accepted
time: 1ms
memory: 16160kb

input:

10000
-5 67
6 53
7 -2
-3 35
-8 57
40 -13
58 33
15 50
-8 -19
68 44
64 57
37 50
55 -16
26 -1
31 -21
21 -15
45 25
65 39
43 53
17 44
15 -17
-11 8
4 13
-24 67
36 64
45 56
61 2
-19 1
-21 -6
36 34
45 15
38 -2
61 32
-19 71
67 60
-15 0
2 35
4 48
-23 25
27 -13
-29 24
43 -15
65 58
64 43
-22 -23
30 50
39 -23
39...

output:

121516554520

result:

ok 1 number(s): "121516554520"

Test #29:

score: 0
Accepted
time: 1ms
memory: 14240kb

input:

9999
-34 -19
-145 -35
-134 -13
-130 -35
-30 -35
-95 -39
-170 -21
-159 0
-79 -35
-15 -19
11 -27
-79 -37
15 -9
-51 -2
-115 4
-62 -34
-177 -31
-87 -13
-123 -22
-1 -23
-120 -27
-154 4
-137 -21
-15 -28
-8 2
-106 -11
-4 1
-47 1
-112 -37
-125 -5
-109 -12
-143 -44
-43 5
-19 -24
-38 -15
-25 -9
-138 3
-166 -3...

output:

67008499120

result:

ok 1 number(s): "67008499120"

Test #30:

score: 0
Accepted
time: 171ms
memory: 27928kb

input:

499998
-180036999 466647
546376895 -274191
-759132786 -571704
13462383 52379
999043121 6901
-671182806 -659244
-76720384 225530
531060421 -359935
407711301 98395
300237205 -145349
885976725 -608093
319681738 -29924
742182593 -891785
897909385 -474679
-177003169 275039
304424945 68603
849887326 -6715...

output:

0

result:

ok 1 number(s): "0"

Test #31:

score: 0
Accepted
time: 1ms
memory: 16080kb

input:

10
166026482 832001424
663929201 334098705
-229711492 -559541988
802071362 195956544
543275974 213445478
45373255 711348197
-727614211 -61639269
-91569331 -697684149
-75571576 -405402072
62570585 -543544233

output:

114

result:

ok 1 number(s): "114"

Test #32:

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

input:

8
42216117 616406995
261826201 -692170641
-502267659 71923219
-695544180 265199740
-185570643 775173277
190485873 -105532847
976662583 22665741
19292202 980036122

output:

47

result:

ok 1 number(s): "47"

Test #33:

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

input:

9
137895386 -652297896
381226682 218530664
-69114208 -320192944
177268437 -691670947
419323155 -449616229
39671460 -80573048
229796057 67100039
85119104 -474426256
-149865795 -400944531

output:

70

result:

ok 1 number(s): "70"

Test #34:

score: 0
Accepted
time: 123ms
memory: 29520kb

input:

499998
-148514130 410127030
250777101 -479766821
-812093982 168158934
-88612015 -639230131
68254368 -144790976
734310736 -18352106
285771591 -620516891
133941470 272937488
-502271425 490173839
374285063 -577804317
-124732179 371216877
599201819 302132777
-597450071 -351285685
873607299 -46502577
339...

output:

13928026996625138

result:

ok 1 number(s): "13928026996625138"

Test #35:

score: 0
Accepted
time: 140ms
memory: 29520kb

input:

499998
-63878687 541097821
-111901249 239040699
-94270400 -305664352
87612771 -828053845
302553604 -428878366
-923276410 44701774
37376350 -715736772
576720958 -365080298
32991904 214541942
524286493 -385837495
579260791 375887417
195849822 444241664
81124173 -533021023
22202479 144972063
443313611 ...

output:

13892975848363715

result:

ok 1 number(s): "13892975848363715"

Test #36:

score: 0
Accepted
time: 181ms
memory: 29320kb

input:

500000
122345378 -664770190
-616980514 296674848
-236533972 106847166
32382348 327652874
-604867541 244889835
-577136105 -280507737
-22739297 128055825
-202654251 -245241277
482413205 -214166729
-157869444 -400132254
783515682 178921548
378718057 -7780653
-584128028 -111442438
-735997571 45284331
61...

output:

13887183745220121

result:

ok 1 number(s): "13887183745220121"

Test #37:

score: 0
Accepted
time: 181ms
memory: 29392kb

input:

499999
148830873 -307392609
326861376 72049242
593104343 197958519
434990026 -455784390
102364252 -865514648
-262468945 -326648063
378236658 -144223794
188690223 -690564795
-721613891 118344189
-155750053 -417651461
-196281065 153294409
-376168434 268878858
809426324 165442886
143479414 78279418
227...

output:

13889858915641519

result:

ok 1 number(s): "13889858915641519"

Test #38:

score: 0
Accepted
time: 187ms
memory: 29520kb

input:

500000
-430724925 -99811915
152068662 -600097074
-752223403 -45302629
-10099387 -791672445
8403405 -331379707
94985137 -22062303
-953244323 40557901
533689968 -16458830
68264974 -656280234
-397217458 -451079316
364445912 499169738
945188900 -39167816
-71949252 305342578
-682501076 232577472
14790596...

output:

13887844643863157

result:

ok 1 number(s): "13887844643863157"

Test #39:

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

input:

9
0 -3
1 -4
1 -1
0 -4
0 -5
1 -3
1 -2
0 -1
0 -2

output:

59

result:

ok 1 number(s): "59"

Test #40:

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

input:

9999
10 -19
-34 -8
23 -50
-53 -5
-61 0
-45 -20
23 -66
-20 -50
-31 -78
16 1
-11 -84
5 -85
-43 -35
-27 9
-60 4
-34 -20
-64 -26
-14 -7
4 -86
-15 -5
-40 -33
15 -51
9 9
-31 -29
-65 -25
-31 -28
-35 -71
7 -77
10 -33
-15 0
-6 -83
-17 -28
-2 -45
-31 1
-21 -26
-21 -35
5 -19
-57 -48
-61 -29
9 -71
-62 3
17 -64
...

output:

121481280579

result:

ok 1 number(s): "121481280579"

Test #41:

score: 0
Accepted
time: 1ms
memory: 16284kb

input:

10000
-41 37
68 36
84 25
110 26
136 47
70 42
9 -1
-31 41
1 28
128 5
113 46
43 39
109 45
-45 1
126 4
63 17
16 34
54 8
3 39
3 47
96 43
5 36
88 31
133 0
41 16
150 8
103 8
47 34
107 33
-3 8
-25 37
23 9
6 28
114 17
101 42
-29 32
50 44
-5 24
122 36
79 33
46 26
37 12
50 39
13 25
125 37
69 25
70 32
62 5
14 ...

output:

67026289220

result:

ok 1 number(s): "67026289220"

Test #42:

score: 0
Accepted
time: 158ms
memory: 27992kb

input:

499999
-467239570 861530
643458011 245447
540413402 -13838
775301546 801248
120750071 848871
-877898425 1061207
-778122046 1079264
-236262370 1406128
669451423 279833
698046858 468404
12907820 860420
519581359 -158595
146217574 867502
85040477 623709
394808799 157743
-74674947 754105
-122437943 1048...

output:

0

result:

ok 1 number(s): "0"

Test #43:

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

input:

3
-1000000000 -1000000000
1000000000 1000000000
1000000000 -1000000000

output:

1

result:

ok 1 number(s): "1"