QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#626314#4236. Triangular Logsnickbelov#RE 3334ms62712kbC++2012.0kb2024-10-10 03:40:522024-10-10 03:40:53

Judging History

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

  • [2024-10-10 03:40:53]
  • 评测
  • 测评结果:RE
  • 用时:3334ms
  • 内存:62712kb
  • [2024-10-10 03:40:52]
  • 提交

answer

#include <vector>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;

struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;

template<bool HAS_QUERY, class B, class T, class F, class I>
struct wavelet_tree_base{
	int n, lg;
	B sigma;
	vector<vector<int>> data;
	vector<vector<T>> aggregate;
	F TT; // commutative group operation
	T T_id; // commutative group identity
	I Tinv; // commutative group inverse
	wavelet_tree_base(F TT, T T_id, I Tinv): TT(TT), T_id(T_id), Tinv(Tinv){ }
	wavelet_tree_base &operator=(const wavelet_tree_base &wt){
		n = wt.n;
		lg = wt.lg;
		sigma = wt.sigma;
		data = wt.data;
		return *this;
	}
	// O(n * log(sigma)) time and O(n * log(sigma)) memory
	void build(const vector<B> &key, B sigma){
		static_assert(!HAS_QUERY);
		assert(sigma > 0);
		for(auto x: key) assert(0 <= x && x < sigma);
		n = (int)key.size();
		this->sigma = sigma;
		lg = __lg(sigma) + (B(1) << lg != sigma) + 1;
		data.assign(lg, vector<int>(n + 1));
		vector<B> cur = key, next(n);
		for(auto h = lg; h --;){
			for(auto i = 0; i < n; ++ i) data[h][i + 1] = data[h][i] + (~cur[i] >> h & 1);
			array it{next.begin(), next.begin() + data[h][n]};
			for(auto i = 0; i < n; ++ i) *it[data[h][i] == data[h][i + 1]] ++ = cur[i];
			swap(cur, next);
		}
	}
	// O(n * log(sigma)) time and O(n * log(sigma)) memory
	template<class U>
	void build(const vector<B> &key, B sigma, const vector<U> &value){
		static_assert(HAS_QUERY);
		assert(sigma > 0);
		for(auto x: key) assert(0 <= x && x < sigma);
		n = (int)key.size();
		this->sigma = sigma;
		lg = __lg(sigma) + (B(1) << lg != sigma) + 1;
		data.assign(lg, vector<int>(n + 1));
		aggregate.assign(lg + 1, vector<T>(n + 1, T_id));
		vector<pair<B, T>> cur(n), next(n);
		for(auto i = 0; i < n; ++ i) cur[i] = {key[i], value[i]};
		for(auto h = lg; h --;){
			for(auto i = 0; i < n; ++ i) data[h][i + 1] = data[h][i] + (~cur[i].first >> h & 1);
			array it{next.begin(), next.begin() + data[h][n]};
			for(auto i = 0; i < n; ++ i){
				*it[data[h][i] == data[h][i + 1]] ++ = cur[i];
				aggregate[h + 1][i + 1] = data[h][i] == data[h][i + 1] ? aggregate[h + 1][i] : TT(aggregate[h + 1][i], cur[i].second);
			}
			swap(cur, next);
		}
		for(auto i = 0; i < n; ++ i) aggregate[0][i + 1] = TT(aggregate[0][i], cur[i].second);
	}
	// Returns the frequency of x in the interval [ql, qr)
	// O(log(sigma))
	int freq(int ql, int qr, int x) const{
		assert(0 <= ql && ql <= qr && qr <= n);
		assert(0 <= x);
		if(ql == qr || sigma <= x) return 0;
		for(auto h = lg; h --; ){
			if(~x >> h & 1) ql = data[h][ql], qr = data[h][qr];
			else ql += data[h][n] - data[h][ql], qr += data[h][n] - data[h][qr];
		}
		return qr - ql;
	}
	// Returns the frequency of x in the interval [ql, qr), along with the sum of their values
	// O(log(sigma))
	pair<int, T> freq_query(int ql, int qr, int x) const{
		static_assert(HAS_QUERY);
		assert(0 <= ql && ql <= qr && qr <= n);
		assert(0 <= x);
		if(ql == qr || sigma <= x) return {0, T_id};
		for(auto h = lg; h --; ){
			if(~x >> h & 1) ql = data[h][ql], qr = data[h][qr];
			else ql += data[h][n] - data[h][ql], qr += data[h][n] - data[h][qr];
		}
		return {qr - ql, TT(aggregate[0][qr], Tinv(aggregate[0][ql]))};
	}
	// Returns the number of occurrences of numbers in [0, xr) in the interval [ql, qr)
	// O(log(sigma))
	int count(int ql, int qr, B xr) const{
		assert(0 <= ql && ql <= qr && qr <= n);
		assert(0 <= xr);
		if(sigma <= xr) return qr - ql;
		if(xr == 0) return 0;
		int cnt = 0;
		for(auto h = lg; h --; ){
			if(~xr >> h & 1) ql = data[h][ql], qr = data[h][qr];
			else{
				cnt += data[h][qr] - data[h][ql];
				ql += data[h][n] - data[h][ql], qr += data[h][n] - data[h][qr];
			}
		}
		return cnt;
	}
	// Returns the number of occurrences of numbers in [0, xr) in the interval [ql, qr), along with the sum of their values
	// O(log(sigma))
	pair<int, T> count_query(int ql, int qr, B xr) const{
		static_assert(HAS_QUERY);
		assert(0 <= ql && ql <= qr && qr <= n);
		assert(0 <= xr);
		if(xr == 0) return {0, T_id};
		xr = min(sigma, xr);
		int cnt = 0;
		T sum = T_id;
		for(auto h = lg; h --; ){
			if(~xr >> h & 1) ql = data[h][ql], qr = data[h][qr];
			else{
				cnt += data[h][qr] - data[h][ql];
				sum = TT(sum, TT(aggregate[h + 1][qr], Tinv(aggregate[h + 1][ql])));
				ql += data[h][n] - data[h][ql], qr += data[h][n] - data[h][qr];
			}
		}
		return {cnt, sum};
	}
	// Returns the number of occurrences of numbers in [xl, xr) in the interval [ql, qr)
	// O(log(sigma))
	int count(int ql, int qr, B xl, B xr) const{
		assert(xl <= xr);
		if(xl == xr) return 0;
		return count(ql, qr, xr) - count(ql, qr, xl);
	}
	// Returns the number of occurrences of numbers in [xl, xr) in the interval [ql, qr), along with the sum of their values
	// O(log(sigma))
	pair<int, T> count_query(int ql, int qr, B xl, B xr) const{
		static_assert(HAS_QUERY);
		assert(xl <= xr);
		if(xl == xr) return {0, T_id};
		auto [lcnt, lsum] = count_query(ql, qr, xl);
		auto [rcnt, rsum] = count_query(ql, qr, xr);
		return {rcnt - lcnt, TT(rsum, Tinv(lsum))};
	}
	// Find the k-th smallest element in the interval [ql, qr), sigma if no such element
	// O(log(sigma))
	B find_by_order(int ql, int qr, int k) const{
		assert(0 <= k);
		if(k >= qr - ql) return sigma;
		B x = 0;
		for(auto h = lg; h --; ){
			if(k < data[h][qr] - data[h][ql]) ql = data[h][ql], qr = data[h][qr];
			else{
				k -= data[h][qr] - data[h][ql];
				x |= (B)1 << h;
				ql += data[h][n] - data[h][ql], qr += data[h][n] - data[h][qr];
			}
		}
		return x;
	}
	// Find the k-th smallest element in the interval [ql, qr), sigma if no such element, along with the sum of values of the k smallest elements (prioritizing smaller index)
	// O(log(sigma))
	pair<B, T> find_by_order_query(int ql, int qr, int k) const{
		assert(0 <= k);
		k = min(k, qr - ql);
		B x = 0;
		T sum = T_id;
		for(auto h = lg; h --; ){
			if(k < data[h][qr] - data[h][ql]) ql = data[h][ql], qr = data[h][qr];
			else {
				k -= data[h][qr] - data[h][ql];
				x |= (B)1 << h;
				sum = TT(sum, TT(aggregate[h + 1][qr], Tinv(aggregate[h + 1][ql])));
				ql += data[h][n] - data[h][ql], qr += data[h][n] - data[h][qr];
			}
		}
		return {x, TT(sum, TT(aggregate[0][ql + k], Tinv(aggregate[0][ql])))};
	}
	// Find the k-th smallest element in the interval [ql, qr) among elements >= xl, sigma if no such element
	// O(log(sigma))
	B find_by_order(int ql, int qr, B xl, int k) const{
		assert(0 <= ql && ql <= qr && qr <= n);
		assert(0 <= xl && 0 <= k);
		if(xl >= sigma) return sigma;
		k += count(ql, qr, 0, xl);
		if(k >= qr - ql) return sigma;
		return find_by_order(ql, qr, k);
	}
	// Find the k-th smallest element in the interval [ql, qr) among elements >= xl, sigma if no such element, along with the sum of values of the k smallest elements (prioritizing smaller index)
	// O(log(sigma))
	pair<B, T> find_by_order_query(int ql, int qr, B xl, int k) const{
		assert(0 <= ql && ql <= qr && qr <= n);
		assert(0 <= xl && 0 <= k);
		if(xl >= sigma) return {sigma, T_id};
		auto [cnt, sum] = count_query(ql, qr, 0, xl);
		k += cnt;
		auto [x, sum2] = find_by_order_query(ql, qr, k);
		return {x, TT(sum2, Tinv(sum))};
	}
	// Find the smallest element >= x, sigma if no such element
	// O(log(sigma))
	B lower_bound(int ql, int qr, B x) const{
		assert(0 <= x);
		return find_by_order(ql, qr, x, 0);
	}
	// Find the smallest element > x, sigma if no such element
	// O(log(sigma))
	B upper_bound(int ql, int qr, B x) const{
		assert(0 <= x);
		return find_by_order(ql, qr, x + 1, 0);
	}
	// Find the largest element <= x, -1 if no such element
	// O(log(sigma))
	B reverse_lower_bound(int ql, int qr, B x) const{
		assert(0 <= x);
		int cnt = count(ql, qr, x);
		return cnt ? find_by_order(ql, qr, cnt - 1) : -1;
	}
	// Find the largest element < x, -1 if no such element
	// O(log(sigma))
	B reverse_upper_bound(int ql, int qr, B x) const{
		assert(0 <= x);
		int cnt = count(ql, qr, x + 1);
		return cnt ? find_by_order(ql, qr, cnt - 1) : -1;
	}
};

template<class B>
auto make_wavelet_tree(){
	return wavelet_tree_base<false, B, int, plus<>, negate<>>(plus<>(), 0, negate<>());
}
// Supports query
template<class B, class T = long long, class F = plus<>, class I = negate<>>
auto make_Q_wavelet_tree(F TT = plus<>(), T T_id = 0, I Tinv = negate<>()){
	return wavelet_tree_base<true, B, T, F, I>(TT, T_id, Tinv);
}



struct Tree{int x,y,h;};
struct QR{int x1,y1,x2,y2;};
bool operator<(Tree t1,Tree t2){
    return t1.x<t2.x;
}

void run()
{
    int n,q; cin >> n >> q;

    vector<Tree> v(n);
    vector<QR> Q(q);

    set<int> st;
    for(int i : rep(n))
        cin >> v[i].x >> v[i].y >> v[i].h, st.insert(v[i].x);
    for(int i : rep(q))
        cin >> Q[i].x1 >> Q[i].y1 >> Q[i].x2 >> Q[i].y2, st.insert(Q[i].x1), st.insert(Q[i].x2);

    sort(A(v));
    // for(auto [x,y,h] : v)
    //     cout << x << " " << y << " " << h << endl;
    vll a(n),b(n),xarr(n);
    for(int i : rep(n)){
        a[i]=v[i].y;
        b[i]=v[i].h;
        xarr[i]=v[i].x;
    }

    auto wv = make_Q_wavelet_tree<ll>();
    wv.build(a,(ll)1e9,b);

    const int N = 50;
    for(auto [x1,y1,x2,y2] : Q){
        auto lb = ranges::lower_bound(xarr,x1);
        auto ub = ranges::upper_bound(xarr,x2);

        int l = lb-xarr.begin(),r=ub-xarr.begin();
        // cout << "\t\t" << l << " " << r << endl;
        // cout << "\t" << x1 << " " << x2 << endl;
        int cnt = wv.count(l,r,y1,y2+1);

        if(cnt>N)
            cout << "1\n";
        else{
            // Find the k-th smallest element in the interval [ql, qr) among elements >= xl, sigma if no such element, along with the sum of values of the k smallest elements (prioritizing smaller index)
	        // O(log(sigma))
            vll v;
            for(int i : rep(cnt)){
                auto res = wv.find_by_order_query(l,r,y1,i+1);
                v.push_back(res.second);
            }

            for(int i : per(1,len(v))) v[i] -= v[i-1];
            ranges::sort(v);

            bool good = false;
            for(int i : rep(2,len(v))){
                if(v[i]<v[i-1]+v[i-2]) {good=true;break;}
            }
            cout << good << "\n";
            // cout << "\t" << cnt << endl;
            // cout << "\t", ranges::copy(v,oit<ll>()),cout<<endl;
        }
    }
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    run();
}

详细

Test #1:

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

input:

9 5
1 3 3
2 3 1
3 3 4
1 2 1
2 2 5
3 2 9
1 1 2
2 1 6
3 1 5
1 1 1 2
1 1 2 2
1 1 1 3
1 2 3 2
1 1 3 3

output:

0
1
0
0
1

result:

ok 5 lines

Test #2:

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

input:

481 1
8 6788 8975
24 6552 2668
26 7948 4730
40 531 9805
110 1914 1916
164 7073 3371
165 6293 7756
170 9946 2003
179 9654 1700
215 6447 2229
221 3149 3030
242 1999 6843
242 5764 3163
249 3716 8634
250 6801 9317
260 2741 4273
282 5436 4836
284 3951 6483
288 4812 76
375 9004 5492
380 5627 5929
391 6385...

output:

1

result:

ok single line: '1'

Test #3:

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

input:

378 1
62730 50925 80731
92666 77280 61521
29236 67032 7889
35986 96802 8763
13313 49918 83582
51842 66775 47834
2286 12925 41106
39790 6698 15243
65145 56379 68496
35570 809 525
39834 16723 48002
77230 16273 16032
52615 7621 77300
92267 82517 39917
13170 89084 77751
45638 23868 49631
7758 71381 5191...

output:

1

result:

ok single line: '1'

Test #4:

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

input:

100000 100000
299999993 206450345 26023928
334281171 300000008 18107965
318653732 299999990 82338399
299999997 393028366 37212808
299999992 208114125 82126189
300000002 303613195 34463905
270033576 299999993 49200970
300000003 249755524 5829381
300000003 367329175 12867359
300000009 337452692 131045...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #5:

score: 0
Accepted
time: 106ms
memory: 50828kb

input:

100000 100000
299999990 299999990 40343876
299999990 299999991 75128878
299999990 299999992 54630219
299999990 299999993 2733654
299999990 299999994 46236519
299999990 299999995 98430004
299999990 299999996 48355189
299999990 299999997 85287882
299999990 299999998 83938086
299999990 299999999 739070...

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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 100000 lines

Test #6:

score: 0
Accepted
time: 222ms
memory: 62108kb

input:

100000 100000
586649484 999402721 770254678
406977522 613559 332964690
987164 445493717 518079399
249557488 999424331 597100212
143514230 999205612 56986976
933588533 509797 769263555
696911 930171165 201130067
833170 541105172 912457971
145501 423684829 612968794
999276416 167526939 136454621
70428...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #7:

score: 0
Accepted
time: 220ms
memory: 62096kb

input:

100000 100000
341071 873501571 1101
59980263 526804 9
297715277 999186682 197674
709891830 999005915 346
999712634 250379232 3158
999959502 879534904 11273
253455643 999864444 49222
427866822 999577133 210191465
729566332 999548170 14
657471525 144302 846059
319542083 999756032 6275
219750473 765955...

output:

0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
...

result:

ok 100000 lines

Test #8:

score: 0
Accepted
time: 352ms
memory: 56664kb

input:

100000 100000
330451877 499036874 19421
148915905 333179772 5692
556747855 500052531 51199
580265032 499999972 188350435
380806313 500000128 65
500046272 499999847 2336904
496578778 500015254 22900850
499999993 473970765 17403806
499999989 499163205 2
499999946 499999562 19056
671553596 327120722 53...

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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 100000 lines

Test #9:

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

input:

44 1
1 1 1
2 2 1
3 3 2
4 4 3
5 5 5
6 6 8
7 7 13
8 8 21
9 9 34
10 10 55
11 11 89
12 12 144
13 13 233
14 14 377
15 15 610
16 16 987
17 17 1597
18 18 2584
19 19 4181
20 20 6765
21 21 10946
22 22 17711
23 23 28657
24 24 46368
25 25 75025
26 26 121393
27 27 196418
28 28 317811
29 29 514229
30 30 832040
3...

output:

0

result:

ok single line: '0'

Test #10:

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

input:

45 1
1 1 1
2 2 1
3 3 2
4 4 3
5 5 5
6 6 8
7 7 13
8 8 21
9 9 34
10 10 55
11 11 89
12 12 144
13 13 233
14 14 377
15 15 610
16 16 987
17 17 1597
18 18 2584
19 19 4181
20 20 6765
21 21 10946
22 22 17711
23 23 28657
24 24 46368
25 25 75025
26 26 121393
27 27 196418
28 28 317811
29 29 514229
30 30 832040
3...

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 382ms
memory: 62580kb

input:

100000 100000
51117683 475559198 55
813845469 801994152 34
100675101 138896713 75025
674464384 463090901 55
902054575 869434307 514229
605417726 228399535 377
169256387 179944933 121393
512055115 920070240 3
9910025 214361011 1597
136966996 202823334 5
809276926 864634761 144
349042632 12808782 34
9...

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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
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 100000 lines

Test #12:

score: 0
Accepted
time: 3334ms
memory: 62596kb

input:

100000 100000
22278009 297645636 5702887
216682777 711802229 6765
428165552 28960704 4181
897637309 6584268 701408733
489121330 334310790 46368
82789029 688310692 377
591766279 602483915 2
507641379 304240670 317811
509164606 712250388 75025
507760780 110079699 2
852079642 843093685 75025
472835533 ...

output:

1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #13:

score: 0
Accepted
time: 307ms
memory: 57804kb

input:

100000 100000
1582278 1577287 1
4746834 1577287 2
7911390 1577287 3
11075946 1577287 5
14240502 1577287 8
17405058 1577287 13
20569614 1577287 1
23734170 1577287 2
26898726 1577287 3
30063282 1577287 5
33227838 1577287 8
36392394 1577287 13
39556950 1577287 1
42721506 1577287 2
45886062 1577287 3
49...

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
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #14:

score: 0
Accepted
time: 147ms
memory: 51956kb

input:

99990 2222
808609143 791567776 1
808919711 791796567 1
808069792 791902659 2
808104504 791739356 3
808886088 791504796 5
808821181 791960293 8
808449111 792186438 13
808952530 791418710 21
808950482 791838071 34
808524778 792132088 55
809023687 792082261 89
808562602 791380376 144
808076738 79176470...

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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 2222 lines

Test #15:

score: 0
Accepted
time: 302ms
memory: 62648kb

input:

100000 100000
629909712 629909712 398
872281243 872281243 10024809
816785764 816785764 247172
657528859 657528859 53254731
228201517 228201517 2439818
565718267 565718267 28473
443534726 443534726 98059
88387904 88387904 199
186944602 186944602 2169907
415004779 415004779 5
661135835 661135835 2
630...

output:

0
0
0
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
1
0
1
1
1
1
1
0
0
1
0
1
0
1
1
1
1
0
1
0
1
1
1
1
1
1
0
0
1
1
0
1
1
1
0
1
1
0
1
0
0
1
1
1
0
1
1
1
1
1
0
0
1
1
0
0
0
1
0
0
1
1
1
0
1
1
1
1
0
1
1
1
0
0
1
1
1
1
1
0
1
0
1
1
1
1
1
0
1
1
0
0
0
1
0
0
1
0
0
0
1
0
1
1
1
0
1
1
1
0
1
1
0
1
0
1
1
0
0
0
1
1
0
1
1
0
0
1
1
0
...

result:

ok 100000 lines

Test #16:

score: 0
Accepted
time: 218ms
memory: 62712kb

input:

100000 100000
491385337 500000000 20
416737373 500000000 871
43347252 500000000 12283172
296433756 500000000 172559
926353666 500000000 73621320
384358430 500000000 569492
151794891 500000000 27446626
485516856 500000000 1162161
833453781 500000000 104
136381889 500000000 601654
944609596 500000000 ...

output:

0
0
1
1
0
1
1
0
1
0
1
1
1
0
1
0
0
0
1
1
0
1
0
0
0
0
1
1
0
0
1
1
0
1
1
0
1
1
0
1
1
1
1
0
0
0
1
1
0
0
1
0
1
0
1
0
1
1
0
0
1
0
0
0
0
0
1
1
1
1
1
1
1
0
0
1
0
0
0
0
1
1
0
1
0
0
0
0
1
0
1
0
0
0
0
0
1
1
0
0
0
0
1
0
1
1
0
1
1
1
0
0
1
1
0
1
1
1
0
1
0
1
0
0
0
1
1
0
1
1
0
0
1
1
0
0
0
1
0
0
0
0
1
0
0
1
0
1
0
0
...

result:

ok 100000 lines

Test #17:

score: 0
Accepted
time: 198ms
memory: 58032kb

input:

100000 100000
500000000 835730809 8611019
500000000 55914010 23902
500000000 841175146 40133470
500000000 427205129 609
500000000 722589256 35603
500000000 607575657 465243375
500000000 589669151 85667528
500000000 386727444 442780
500000000 772072358 61506
500000000 607134054 1463781
500000000 7349...

output:

1
1
1
0
1
0
0
0
1
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
0
0
1
1
0
1
0
0
1
0
1
1
0
0
1
0
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
0
0
1
0
1
1
0
0
1
0
1
0
1
1
1
0
1
0
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
0
0
0
1
0
1
1
0
0
0
1
0
1
0
1
1
0
0
1
0
1
1
1
0
0
1
0
0
1
1
0
0
1
1
1
0
0
0
1
0
0
0
0
1
1
0
0
0
0
...

result:

ok 100000 lines

Test #18:

score: 0
Accepted
time: 423ms
memory: 62584kb

input:

100000 100000
559205749 287135929 450126584
758119461 184774699 598200561
414446193 374292451 385550826
358111719 30532876 545952173
709623739 844720071 407013389
263952910 421519775 344566912
811746771 724951475 638700399
300679092 156847316 335763182
181460320 661477907 662719804
280155732 2092322...

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
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 100000 lines

Test #19:

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

input:

45 2
1 1 1
2 2 1
3 3 2
4 4 3
5 5 5
6 6 8
7 7 13
8 8 21
9 9 34
10 10 55
11 11 89
12 12 144
13 13 233
14 14 377
15 15 610
16 16 987
17 17 1597
18 18 2584
19 19 4181
20 20 6765
21 21 10946
22 22 17711
23 23 28657
24 24 46368
25 25 75025
26 26 121393
27 27 196418
28 28 317811
29 29 514229
30 30 832040
3...

output:

0
1

result:

ok 2 lines

Test #20:

score: -100
Runtime Error

input:

100000 100000
129156744 1000000000 292317
1000000000 301262190 26
713069171 1 29401
1000000000 921487600 752
491313490 1 2
384053173 1 6020642
1000000000 532704708 238698
762472640 1 23
1000000000 82407673 14543
994720640 1000000000 5
3211241 1000000000 117626
983507192 1000000000 5904
1000000000 21...

output:


result: