QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#222035#7608. Cliquesucup-team088#AC ✓549ms140588kbC++1715.6kb2023-10-21 15:31:102023-10-21 15:31:10

Judging History

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

  • [2023-10-21 15:31:10]
  • 评测
  • 测评结果:AC
  • 用时:549ms
  • 内存:140588kb
  • [2023-10-21 15:31:10]
  • 提交

answer

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
#include<array>
#include<chrono>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
//ll mod = 1;
//constexpr ll mod = 998244353;
constexpr ll mod = 1000000007;
const int mod17 = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int>P;

#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;

using ld = double;
typedef pair<ld, ld> LDP;
const ld eps = 1e-10;
const ld pi = acosl(-1.0);

template<typename T>
void chmin(T& a, T b) {
    a = min(a, b);
}
template<typename T>
void chmax(T& a, T b) {
    a = max(a, b);
}
template<typename T>
vector<T> vmerge(vector<T>& a, vector<T>& b) {
    vector<T> res;
    int ida = 0, idb = 0;
    while (ida < a.size() || idb < b.size()) {
        if (idb == b.size()) {
            res.push_back(a[ida]); ida++;
        }
        else if (ida == a.size()) {
            res.push_back(b[idb]); idb++;
        }
        else {
            if (a[ida] < b[idb]) {
                res.push_back(a[ida]); ida++;
            }
            else {
                res.push_back(b[idb]); idb++;
            }
        }
    }
    return res;
}
template<typename T>
void cinarray(vector<T>& v) {
    rep(i, v.size())cin >> v[i];
}
template<typename T>
void coutarray(vector<T>& v) {
    rep(i, v.size()) {
        if (i > 0)cout << " "; cout << v[i];
    }
    cout << "\n";
}
ll mod_pow(ll x, ll n, ll m = mod) {
    if (n < 0) {
        ll res = mod_pow(x, -n, m);
        return mod_pow(res, m - 2, m);
    }
    if (abs(x) >= m)x %= m;
    if (x < 0)x += m;
    //if (x == 0)return 0;
    ll res = 1;
    while (n) {
        if (n & 1)res = res * x % m;
        x = x * x % m; n >>= 1;
    }
    return res;
}
//mod should be <2^31
struct modint {
    int n;
    modint() :n(0) { ; }
    modint(ll m) {
        if (m < 0 || mod <= m) {
            m %= mod; if (m < 0)m += mod;
        }
        n = m;
    }
    operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
bool operator<(modint a, modint b) { return a.n < b.n; }
modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= (int)mod; return a; }
modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0)a.n += (int)mod; return a; }
modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, ll n) {
    if (n == 0)return modint(1);
    modint res = (a * a) ^ (n / 2);
    if (n % 2)res = res * a;
    return res;
}

ll inv(ll a, ll p) {
    return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
modint operator/=(modint& a, modint b) { a = a / b; return a; }
const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
    fact[0] = modint(1);
    for (int i = 0; i < max_n - 1; i++) {
        fact[i + 1] = fact[i] * modint(i + 1);
    }
    factinv[max_n - 1] = modint(1) / fact[max_n - 1];
    for (int i = max_n - 2; i >= 0; i--) {
        factinv[i] = factinv[i + 1] * modint(i + 1);
    }
}
modint comb(int a, int b) {
    if (a < 0 || b < 0 || a < b)return 0;
    return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
    if (a < 0 || b < 0 || a < b)return 0;
    return fact[a] * factinv[a - b];
}

ll gcd(ll a, ll b) {
    a = abs(a); b = abs(b);
    if (a < b)swap(a, b);
    while (b) {
        ll r = a % b; a = b; b = r;
    }
    return a;
}
template<typename T>
void addv(vector<T>& v, int loc, T val) {
    if (loc >= v.size())v.resize(loc + 1, 0);
    v[loc] += val;
}
/*const int mn = 2000005;
bool isp[mn];
vector<int> ps;
void init() {
    fill(isp + 2, isp + mn, true);
    for (int i = 2; i < mn; i++) {
        if (!isp[i])continue;
        ps.push_back(i);
        for (int j = 2 * i; j < mn; j += i) {
            isp[j] = false;
        }
    }
}*/

//[,val)
template<typename T>
auto prev_itr(set<T>& st, T val) {
    auto res = st.lower_bound(val);
    if (res == st.begin())return st.end();
    res--; return res;
}

//[val,)
template<typename T>
auto next_itr(set<T>& st, T val) {
    auto res = st.lower_bound(val);
    return res;
}
using mP = pair<modint, modint>;
mP operator+(mP a, mP b) {
    return { a.first + b.first,a.second + b.second };
}
mP operator+=(mP& a, mP b) {
    a = a + b; return a;
}
mP operator-(mP a, mP b) {
    return { a.first - b.first,a.second - b.second };
}
mP operator-=(mP& a, mP b) {
    a = a - b; return a;
}
LP operator+(LP a, LP b) {
    return { a.first + b.first,a.second + b.second };
}
LP operator+=(LP& a, LP b) {
    a = a + b; return a;
}
LP operator-(LP a, LP b) {
    return { a.first - b.first,a.second - b.second };
}
LP operator-=(LP& a, LP b) {
    a = a - b; return a;
}

mt19937 mt(time(0));

const string drul = "DRUL";
string senw = "SENW";
//DRUL,or SENW
//int dx[4] = { 1,0,-1,0 };
//int dy[4] = { 0,1,0,-1 };

//------------------------------------


#define ftt function<T(T,T)>
#define ftu function<T(T,U,int,int)>
#define fuu function<U(U,U)>

template<typename T, typename U>
struct SegT {
private:
	int n;
	vector<T> node;
	vector<U> lazy;
	T et; U eu;
	ftt f;
	ftu g;
	fuu h;
public:
	void init(vector<T> ori, T _et, U _eu, ftt _f, ftu _g, fuu _h) {
		int sz = ori.size();
		et = _et, eu = _eu; f = _f, g = _g, h = _h;
		n = 1;
		while (n < sz)n <<= 1;
		node.resize(2 * n - 1, et);
		lazy.resize(2 * n - 1, eu);
		rep(i, sz) {
			node[i + n - 1] = ori[i];
		}
		per(i, n - 1) {
			node[i] = f(node[2 * i + 1], node[2 * i + 2]);
		}
	}
	SegT() { ; }
	void init(int sz, T _et, U _eu, ftt _f, ftu _g, fuu _h) {
		et = _et, eu = _eu; f = _f, g = _g, h = _h;
		n = 1;
		while (n < sz)n <<= 1;
		node.resize(2 * n - 1, et);
		lazy.resize(2 * n - 1, eu);
	}
	void eval(int k, int l, int r) {
		if (lazy[k] == eu)return;
		node[k] = g(node[k], lazy[k], l, r);
		if (r - l > 1) {
			lazy[2 * k + 1] = h(lazy[k], lazy[2 * k + 1]);
			lazy[2 * k + 2] = h(lazy[k], lazy[2 * k + 2]);
		}
		lazy[k] = eu;
	}
	void add(U x, int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = n;
		eval(k, l, r);
		if (r <= a || b <= l)return;
		if (a <= l && r <= b) {
			lazy[k] = h(x, lazy[k]);
			eval(k, l, r);
		}
		else {
			add(x, a, b, k * 2 + 1, l, (l + r) / 2);
			add(x, a, b, k * 2 + 2, (l + r) / 2, r);
			node[k] = f(node[k * 2 + 1], node[k * 2 + 2]);
		}
	}
	T query(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = n;
		eval(k, l, r);
		if (r <= a || b <= l)return et;
		if (a <= l && r <= b)return node[k];
		else {
			T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
			T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
			return f(vl, vr);
		}
	}
	void update(int loc, T x) {
		int k = 0, l = 0, r = n;
		stack<P> st;
		while (k < n - 1) {
			eval(k, l, r);
			st.push({ l,r });
			if (loc < (l + r) / 2) {
				k = 2 * k + 1;
				r = (l + r) / 2;
			}
			else {
				k = 2 * k + 2;
				l = (l + r) / 2;
			}
		}
		eval(k, l, r);
		st.push({ l,r });
		node[k] = x;
		while (k > 0) {
			k = (k - 1) / 2;
			st.pop();
			l = st.top().first, r = st.top().second;
			eval(2 * k + 1, l, (l + r) / 2);
			eval(2 * k + 2, (l + r) / 2, r);
			node[k] = f(node[2 * k + 1], node[2 * k + 2]);
		}
	}
	//k以上でf(x,node[y+sz-1])をtrueにするような最小のy
	int searchloc(int le, T x, function<bool(T, T)> comp) {
		int k = 0, l = 0, r = n;
		while (k < n - 1) {
			eval(k, l, r);
			int m = (l + r) / 2;
			if (le < m) {
				k = 2 * k + 1; r = m;
			}
			else {
				k = 2 * k + 2; l = m;
			}
		}
		assert(k == le + n - 1);
		eval(k, l, r);
		if (comp(x, node[k]))return le;
		//x=f(x,node[k]);
		while (k > 0) {
			int mem = k;
			k = (k - 1) / 2;
			if (2 * k + 1 == mem) {
				r += r - l;
			}
			else {
				l -= r - l;
			}
			if (2 * k + 1 == mem) {
				eval(2 * k + 2, (l + r) / 2, r);
				if (comp(x, node[2 * k + 2])) {
					k = 2 * k + 2;
					l = (l + r) / 2;
					break;
				}
				//x=f(x,node[2*k+2]);
			}
		}
		if (k == 0)return n;
		while (k < n - 1) {
			eval(2 * k + 1, l, (l + r) / 2);
			eval(2 * k + 2, (l + r) / 2, r);
			if (comp(x, node[2 * k + 1])) {
				k = 2 * k + 1;
				r = (l + r) / 2;
			}
			else {
				k = 2 * k + 2;
				l = (l + r) / 2;
				//x=f(x,node[2*k+1]);
			}
		}
		return k - (n - 1);
	}
};



struct edge {
	int to;
};
using edges = vector<edge>;
using Graph = vector<edges>;
struct HLDecomposition {
	

	struct Chain {
		int depth;
		P parent;//chain number,index
		vector<P> child;//child chain number,parent index
		vector<int> mapfrom;
		SegT<modint, modint> stree;

		Chain() { ; }
		Chain(int n) {
			vector<modint> ori(n, 1);
			function<modint(modint, modint)> f = [&](modint a, modint b) {
				return a + b;
			};
			function<modint(modint, modint, int, int)> g = [&](modint a, modint b, int l, int r) {
				a *= b; return a;
			};
			function<modint(modint, modint)> h = [&](modint a, modint b) {
				return a * b;
			};
			stree.init(ori, 0, 1, f, g, h);
		}
	};
	Graph baseG;
	vector<Chain> chains;
	vector<P> mapto;//raw index->chain number &index
	vector<vector<int>> mapfrom;//chain number & index ->raw index

	HLDecomposition() { ; }
	HLDecomposition(const Graph& g) {
		baseG = g;
		const int n = baseG.size();
		mapto = vector<P>(n, P{ -1,-1 });
		mapfrom.clear();
		vector<int> sz(n, 0);
		int start = 0;
		//int start = -1;
		//rep(i, n)if (baseG[i].size() <= 1) { start = i; break; }
		//assert(start != -1);
		size_check_bfs(start, sz);
		decomposition(start, start, 0, 0, 0, sz);
	}
	int depth(int t) {
		return chains[mapto[t].first].depth;
	}

private:
	void size_check_bfs(int start, vector<int>& sz) {
		const int n = baseG.size();
		queue<P> que;
		que.push({ start,start });
		int cnt = 0; vector<int> ord(n, -1);
		while (!que.empty()) {
			int from, parent;
			tie(from, parent) = que.front(); que.pop();
			ord[cnt++] = from;
			for (edge e : baseG[from]) {
				if (e.to == parent)continue;
				que.push({ e.to,from });
			}
		}
		//assert(cnt == n);
		reverse(all(ord));
		rep(i, n) {
			int from = ord[i];
			sz[from] = 1; for (edge e : baseG[from])sz[from] += sz[e.to];
		}
	}
	int decomposition(int from, int parent, int depth, int pnumber, int pindex, const vector<int>& sz) {
		vector<int> seq;
		bfs(from, parent, seq, sz);
		const int c = chains.size();
		chains.push_back(Chain((int)seq.size()));
		//chains.push_back(Chain());
		chains[c].depth = depth;
		chains[c].parent = { pnumber,pindex };
		rep(i, seq.size()) {
			mapto[seq[i]] = { c,i };
			chains[c].mapfrom.push_back(seq[i]);
		}
		mapfrom.push_back(chains[c].mapfrom);
		rep(i, seq.size()) {
			for (edge e : baseG[seq[i]]) {
				if (mapto[e.to].first != -1)continue;
				int nc = decomposition(e.to, seq[i], depth + 1, c, i, sz);
				chains[c].child.push_back({ nc,i });
			}
		}
		return c;
	}
	void bfs(int from, int parent, vector<int>& seq, const vector<int>& sz) {
		for (;;) {
			seq.push_back(from);
			int best = -1, next = -1;
			for (edge e : baseG[from]) {
				if (e.to == parent)continue;
				if (best < sz[e.to]) {
					best = sz[e.to]; next = e.to;
				}
			}
			if (next == -1)break;
			parent = from; from = next;
		}
	}
	vector<pair<int, P>> all_edge(int u, int v) {
		vector<pair<int, P>> res;
		if (depth(u) > depth(v))swap(u, v);
		while (depth(v) > depth(u)) {
			res.push_back({ mapto[v].first,{ 0,mapto[v].second + 1 } });
			P par = chains[mapto[v].first].parent;
			v = mapfrom[par.first][par.second];
		}
		while (mapto[v].first != mapto[u].first) {
			res.push_back({ mapto[v].first,{ 0,mapto[v].second + 1 } });
			P par = chains[mapto[v].first].parent;
			v = mapfrom[par.first][par.second];
			res.push_back({ mapto[u].first,{ 0,mapto[u].second + 1 } });
			par = chains[mapto[u].first].parent;
			u = mapfrom[par.first][par.second];
		}
		P p = minmax(mapto[v].second, mapto[u].second);
		res.push_back({ mapto[v].first,{ p.first + 1,p.second + 1 } });
		return res;
	}
	vector<pair<int, P>> all_vertice(int u, int v) {
		vector<pair<int, P>> res;
		if (depth(u) > depth(v))swap(u, v);
		while (depth(v) > depth(u)) {
			res.push_back({ mapto[v].first,{ 0,mapto[v].second + 1 } });
			P par = chains[mapto[v].first].parent;
			v = mapfrom[par.first][par.second];
		}
		while (mapto[v].first != mapto[u].first) {
			res.push_back({ mapto[v].first,{ 0,mapto[v].second + 1 } });
			P par = chains[mapto[v].first].parent;
			v = mapfrom[par.first][par.second];
			res.push_back({ mapto[u].first,{ 0,mapto[u].second + 1 } });
			par = chains[mapto[u].first].parent;
			u = mapfrom[par.first][par.second];
		}
		P p = minmax(mapto[v].second, mapto[u].second);
		res.push_back({ mapto[v].first,{ p.first,p.second + 1 } });
		return res;
	}

public:

	int lca(int u, int v) {
		if (depth(u) > depth(v))swap(u, v);
		while (depth(v) > depth(u)) {
			P par = chains[mapto[v].first].parent;
			v = mapfrom[par.first][par.second];
		}
		while (mapto[v].first != mapto[u].first) {
			P par = chains[mapto[v].first].parent;
			v = mapfrom[par.first][par.second];
			par = chains[mapto[u].first].parent;
			u = mapfrom[par.first][par.second];
		}
		if (mapto[v].second < mapto[u].second) {
			return v;
		}
		return u;
	}

	modint vertice_add(int u, int v, modint a) {
		modint res = 0;
		vector<pair<int, P>> vs = all_vertice(u, v);
		rep(i, vs.size()) {
			int id = vs[i].first;
			int l = vs[i].second.first; int r = vs[i].second.second;
			res += chains[id].stree.query(l, r);
			chains[id].stree.add(a, l, r);
		}
		return res;
	}
};


void solve() {
	int n; cin >> n;
	Graph g(n);
	rep(i, n - 1) {
		int a, b; cin >> a >> b; a--; b--;
		g[a].push_back({ b });
		g[b].push_back({ a });
	}
	HLDecomposition hldl(g), hldr(g);
	modint sl = n, sr = n;
	modint inv2 = (1 + mod) / 2;
	int q; cin >> q;
	rep(i, q) {
		char c; cin >> c;
		int a, b; cin >> a >> b; a--; b--;
		if (c == '+') {
			modint val = hldl.vertice_add(a, b,2);
			sl += val;
			val = hldr.vertice_add(a, b, 2);
			sr += val;
			int l = hldr.lca(a, b);
			val = hldr.vertice_add(l, l, inv2);
			sr -= val * inv2;
		}
		else {
			modint val = hldl.vertice_add(a, b, inv2);
			sl -= val*inv2;
			val = hldr.vertice_add(a, b, inv2);
			sr -= val*inv2;
			int l = hldr.lca(a, b);
			val = hldr.vertice_add(l, l, 2);
			sr += val;
		}
		modint ans = sl - sr;
		cout << ans << "\n";
	}
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout << fixed<<setprecision(10);
    //init_f();
    //init();
    //init2();
    //while(true)
    //expr();
    //int t; cin >> t; rep(i, t)
    solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 11836kb

input:

5
1 2
5 1
2 3
4 2
6
+ 4 5
+ 2 2
+ 1 3
- 2 2
+ 2 3
+ 4 4

output:

1
3
7
3
7
9

result:

ok 6 lines

Test #2:

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

input:

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

output:

1
3
7
3
1
3
7
15
7
15
31
63
127
255
257
255
259
515
1027
1283
643
385
769
1537
769
785
865
481
737
369

result:

ok 30 lines

Test #3:

score: 0
Accepted
time: 269ms
memory: 44700kb

input:

131072
3641 72511
10338 18718
8949 15478
79108 62887
42154 28540
65359 102645
93744 48493
3277 103211
43542 61315
93315 118634
24021 57937
31034 436
30411 6208
1388 25159
93424 128520
119820 87281
5860 97559
59648 8225
57244 58766
119685 13716
130165 60958
79806 116338
97486 80167
101963 95499
51263...

output:

1
2
4
8
13
27
43
67
119
215
359
423
847
1167
1935
2447
2975
4511
5023
8639
6911
13759
12991
15103
23295
43775
47999
91647
85375
167295
169343
301695
600703
666239
1332351
2664575
2678911
2687103
5374207
5898495
11731455
11731967
22283263
22807551
21955327
43910399
43911423
44207359
44207360
44469504...

result:

ok 46368 lines

Test #4:

score: 0
Accepted
time: 301ms
memory: 77020kb

input:

131073
52869 122762
63296 22816
9889 23435
9452 109352
95210 125504
104234 105533
42422 123259
31189 77343
88679 25422
13860 61424
49617 27681
71743 44108
2612 55383
89088 79225
49508 86216
45176 26493
60940 104568
10733 11047
118351 29678
6184 107897
69675 73910
39495 78910
14871 125941
64731 68683...

output:

1
3
7
11
15
19
31
35
71
143
287
511
1023
1031
1991
1031
1287
1927
2055
3151
4687
4943
9295
17999
18959
37775
73759
74559
148031
148095
296191
151743
160063
110399
110463
127103
63615
63679
64191
90303
138431
212479
212607
423551
423583
426527
770591
865599
1054015
1794879
3587647
3587903
5168959
743...

result:

ok 38380 lines

Test #5:

score: 0
Accepted
time: 303ms
memory: 79084kb

input:

131072
110424 92279
34180 5104
64611 102341
17972 86901
20410 11042
71530 94889
66017 30180
70335 127390
32167 60823
78004 53470
19518 71917
13638 77859
126902 86404
129728 102154
94425 4299
65248 60503
30607 39590
122443 91908
131032 83134
74541 32476
57016 45547
99821 43007
46700 115397
61041 7605...

output:

1
3
4
8
10
12
18
30
32
43
85
133
267
535
791
927
1567
1663
1791
2111
3391
4031
8063
4031
8063
10111
11263
22527
22543
36879
73487
146959
165391
185871
300559
272655
273183
448031
224015
252431
256527
440847
459279
501791
623647
1069087
1265695
2451487
2455583
4911167
3469375
4341823
4620351
7536767
...

result:

ok 41717 lines

Test #6:

score: 0
Accepted
time: 348ms
memory: 80160kb

input:

131073
67110 38301
121636 116046
93081 73335
44685 130771
105514 33619
39372 105681
75426 78839
116548 46901
69485 76621
124381 35376
22485 127299
100526 68870
59214 63623
65534 67039
7351 74453
99617 88460
99785 107786
105070 57072
122179 1357
125230 70014
95838 127074
119211 24691
41698 112488
502...

output:

1
3
5
11
13
14
18
28
40
52
60
62
122
210
340
532
1032
1192
1448
1968
3393
3391
5471
5631
10303
11071
11199
13183
26239
52223
52735
53759
69375
113407
117503
232191
236287
470271
748799
748807
1410567
2790919
1676807
3155975
6178823
6026759
6068743
12075527
20988423
21185031
42340871
42332419
8409549...

result:

ok 42683 lines

Test #7:

score: 0
Accepted
time: 358ms
memory: 79940kb

input:

131071
73178 110293
100318 26012
15854 39905
73704 8141
15422 88351
37522 86820
75177 113252
27007 40876
114342 57373
114214 99629
77119 106699
111052 54010
7544 43524
6414 93020
81451 90262
65947 86220
34831 11736
54471 103491
42146 26136
11584 28666
50699 22506
114316 26350
106262 53089
31102 8196...

output:

1
3
5
9
4
6
10
18
34
66
85
123
127
255
143
279
559
1007
1535
2559
5023
9375
18655
35167
70335
79039
40031
21599
42079
84063
168127
168831
177919
341759
503295
1006591
1072127
1070079
1976319
2107391
1173503
2347007
4694015
4800511
9601023
18022399
9011199
17563647
34078719
65011711
129564671
1349386...

result:

ok 48590 lines

Test #8:

score: 0
Accepted
time: 374ms
memory: 80908kb

input:

131071
39479 96391
14017 23321
50455 14012
126360 118197
113346 92912
48354 86690
78318 34265
94323 55989
30079 44311
2276 30025
16215 90233
34881 85139
57791 13323
50082 125534
36843 69732
104952 39061
82716 2282
63268 42779
35368 9502
17575 123815
2726 43663
123675 93945
4192 64707
87905 123819
40...

output:

1
3
7
11
23
47
95
111
191
159
319
159
319
321
449
705
1409
2817
1409
2817
2945
5761
11521
11649
23297
46593
62979
96771
96775
190983
381959
762887
1295367
1295623
1296139
2574091
1287051
1549579
2606859
4721419
8950543
17896975
35793935
35810319
71604247
142661655
285274135
570515495
140973600
20810...

result:

ok 48889 lines

Test #9:

score: 0
Accepted
time: 483ms
memory: 138640kb

input:

200000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

1
3
5
6
10
20
25
41
35
67
68
133
137
269
295
347
178
340
436
836
1636
882
1636
3236
6212
8580
4356
8580
16648
16652
32780
65036
65040
65052
99364
197668
391204
391348
395445
395509
329941
325844
594140
602352
602344
602896
603184
1148592
2279408
4507632
8964976
17878384
35706480
69575344
139043504
2...

result:

ok 50000 lines

Test #10:

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

input:

200000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

1
0
1
0
1
3
5
6
9
17
29
53
105
109
219
359
719
687
815
1471
767
799
1567
2815
2819
3395
5895
11015
6407
4099
7747
12099
7747
15043
15299
7811
8067
15427
30467
30483
47891
47923
94515
48051
82915
163811
162675
299939
598947
601155
601027
598883
1173155
2246435
2213667
4327459
8620099
8883779
9411139
...

result:

ok 50000 lines

Test #11:

score: 0
Accepted
time: 469ms
memory: 138688kb

input:

200000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

1
3
4
8
17
33
35
69
71
103
199
391
777
1545
2573
4629
4645
4677
5205
9813
9849
19065
37529
38073
71913
74057
78345
149065
289737
306249
597065
1185097
2340169
4663881
9309769
18601033
18633865
37218441
74387593
74388617
147846281
164639881
299873417
299881609
570361105
111320074
193238035
384761861
...

result:

ok 50000 lines

Test #12:

score: 0
Accepted
time: 390ms
memory: 140588kb

input:

200000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

1
3
7
15
31
63
127
255
511
1023
2047
4095
8191
16383
32767
65535
131071
262143
524287
1048575
2097151
4194303
8388607
16777215
33554431
67108863
134217727
268435455
536870911
73741816
147483633
294967267
589934535
179869064
359738129
719476259
438952512
877905025
755810044
511620082
23240158
4648031...

result:

ok 50000 lines

Test #13:

score: 0
Accepted
time: 5ms
memory: 11840kb

input:

2
2 1
1
+ 1 2

output:

1

result:

ok single line: '1'

Test #14:

score: 0
Accepted
time: 484ms
memory: 139448kb

input:

199995
155591 84519
61935 30297
10507 50670
31433 44852
51946 66366
19875 139938
49384 32594
37301 47996
34365 183321
76049 140453
161840 35668
98447 31470
121808 178617
152466 151593
65823 32363
93866 105853
46225 52952
73205 104232
53556 117961
116263 25709
35865 154071
103869 165665
12601 69007
1...

output:

1
3
7
15
31
63
127
63
65
69
133
201
393
785
1313
2369
4737
9347
18691
22787
23299
14723
29447
58887
116231
232455
232457
464907
929803
931851
1863691
1863707
3727387
7405611
5300267
10543147
21037099
21069899
42139723
84181067
84541579
168427667
302842003
370409619
370934035
370934037
370934039
6397...

result:

ok 49974 lines

Test #15:

score: 0
Accepted
time: 517ms
memory: 139408kb

input:

199905
79361 22628
85515 176871
42721 191047
19249 155911
174279 46395
89532 15935
22410 160311
77636 113388
37333 126483
89841 84166
81187 156956
40438 134742
88864 75960
167049 165084
148066 131259
163069 33947
108538 183436
58206 114505
6039 107228
144690 57925
70292 99711
71839 5183
160709 17106...

output:

1
3
7
15
17
33
67
135
271
135
263
519
1031
2063
4127
8223
16447
32831
65663
65665
131329
262657
262659
524803
1049603
2099203
4198403
8392707
16785411
16801795
33603589
67158021
67223557
67354631
134709255
268926983
537853959
75707904
151415801
298899435
597798863
597815247
187749776
367618841
72735...

result:

ok 50000 lines

Test #16:

score: 0
Accepted
time: 549ms
memory: 139148kb

input:

199939
126810 92434
174421 81735
162986 75711
26318 69965
44031 54588
52970 162790
176803 66069
198642 123421
112371 59917
69715 154951
112429 126181
124836 44060
161984 166636
176647 8286
48943 12663
45982 17218
107525 135492
109734 176034
55893 78212
149096 174588
185790 97850
53570 115245
15674 5...

output:

1
2
5
9
19
23
43
79
151
287
367
639
799
815
1599
3007
2975
3007
5855
5919
11743
20159
20415
37503
42111
21503
39551
21503
40447
38271
20415
10943
20607
20863
20927
40383
40415
78335
153087
290431
290435
293507
578435
575363
574275
1144163
574819
579175
1140327
599399
616807
1206663
2386567
4543111
4...

result:

ok 49970 lines

Test #17:

score: 0
Accepted
time: 523ms
memory: 139396kb

input:

200000
134020 173608
13619 76918
17133 29513
146404 65973
109441 86709
190753 99348
120252 193475
124549 88478
91223 161633
137027 31976
172490 172145
94014 44903
129191 110979
199230 122293
82006 195511
76950 113837
180737 110162
18584 54568
62651 3416
51537 146087
100876 161613
4553 82514
187084 6...

output:

1
3
7
11
12
20
28
32
61
101
165
325
647
1163
2191
4367
8471
16919
33311
66591
133167
266287
528447
528575
1056991
2109791
4219231
8438111
16875871
33751455
33882527
34144671
68288959
69337535
138674879
142869183
285738175
571475199
142950136
142950138
216692211
364176101
431284965
431285093
72625466...

result:

ok 50000 lines

Test #18:

score: 0
Accepted
time: 371ms
memory: 62544kb

input:

199991
131115 127761
128141 9947
118948 199136
194495 52407
3038 150618
109068 296
118921 42906
32966 194326
18727 155009
153415 91730
183299 123049
77426 36132
60131 170134
192268 118595
53024 145284
74390 135856
90091 97771
170069 46155
78532 83748
76184 115369
196830 14441
83234 137528
118706 114...

output:

1
2
4
6
12
20
41
73
145
225
259
267
535
1055
1057
1969
2241
2785
2849
3105
6211
6275
8323
13699
18307
32131
59971
116675
171139
330883
355459
710147
1365507
2708995
2758147
2958851
5776899
11019779
21636611
43198727
86388495
172768015
178017055
196638239
213427775
280561215
560531007
594134591
59441...

result:

ok 49942 lines

Test #19:

score: 0
Accepted
time: 370ms
memory: 59448kb

input:

199921
88253 52631
43472 60168
126943 91568
42376 149650
182742 18220
189063 55458
1983 73802
43527 24362
15388 94498
60070 26890
156887 181370
13959 3538
8673 116293
172414 98912
75585 182988
56402 69400
116203 63483
168182 89766
140594 83130
62023 108013
131617 127308
111490 181754
146979 16032
14...

output:

1
3
5
2
3
6
12
6
10
14
13
21
13
21
35
71
143
287
415
575
1151
575
639
959
963
1923
2563
5123
8707
16899
20995
37891
38019
38275
43395
33155
57091
114179
118275
132103
132105
69641
81929
163849
186385
364577
729153
1441921
1802497
3293441
3817729
7635201
7635715
15271171
16581891
20776195
41551107
82...

result:

ok 49969 lines

Test #20:

score: 0
Accepted
time: 376ms
memory: 61676kb

input:

199961
6566 6320
120135 64612
120403 93339
9289 16098
118401 47489
14946 175740
51984 17767
160551 69679
80762 39816
74519 115327
180551 154037
67164 153772
175897 137890
74592 16932
6311 83607
87740 12379
68295 123078
8740 48267
58674 29448
42492 199128
113955 68509
192499 185731
158313 61660
24163...

output:

1
2
5
11
23
47
95
97
101
197
391
197
389
517
1033
1545
1561
3121
6209
12355
12363
20555
24651
49291
98519
196951
393559
786775
983383
786775
788823
1575263
1576031
2103391
4206719
6836351
13652159
22061247
44122463
44122527
44147167
88294175
88326943
155435807
289800991
290456479
290456991
307234719...

result:

ok 49937 lines

Test #21:

score: 0
Accepted
time: 399ms
memory: 60324kb

input:

199986
197271 19652
144685 60421
178455 136710
192878 14024
116174 39504
89189 150440
111847 47085
137023 135177
49593 188587
99891 165060
17432 133195
154398 95839
144244 77014
69862 91980
825 164367
111143 35742
180176 93478
11627 19622
189240 74023
190299 5562
197105 11166
187214 86304
76464 7135...

output:

1
0
1
2
5
11
13
7
11
13
14
26
44
76
148
276
536
1056
2096
2624
5216
10336
20608
41216
41856
82817
82881
82913
85185
42593
21985
39393
78785
39617
39635
76755
77139
39051
77195
150923
299275
299283
299275
365331
497699
991811
992835
995907
1525895
769607
1034183
2067399
4133831
8259399
12552007
21006...

result:

ok 49976 lines

Test #22:

score: 0
Accepted
time: 436ms
memory: 101224kb

input:

199948
127561 156846
73803 21852
177891 61198
173157 58416
53953 155974
172123 176895
131223 39360
42579 13568
76543 165055
60377 9906
29609 74224
91670 35997
145883 152903
87501 87785
20937 160730
83347 21491
51113 8163
147789 36552
150228 133873
171328 56242
19348 43247
191703 65970
9398 21934
913...

output:

1
0
1
3
5
6
11
19
39
47
59
119
135
199
263
527
399
495
927
1503
1759
2655
4703
7263
12991
13119
13375
13503
15807
27775
54911
102015
200831
106623
172159
189567
190079
206463
209279
214911
249727
319871
460159
660863
666111
1299199
2562303
3741951
4987135
5642495
11264255
22528511
28336639
46096895
...

result:

ok 50000 lines

Test #23:

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

input:

200000
19501 72549
169108 68861
17653 94137
54534 18997
89426 140431
65005 45936
113520 161951
134524 74528
144019 85516
107071 102714
5262 143555
53739 24459
88014 114776
175394 81037
193370 162716
100826 143166
3700 134554
195547 29822
120283 155023
114520 164141
23561 189321
26049 175925
179016 1...

output:

1
2
4
6
10
18
34
66
130
258
386
453
837
903
1671
1703
871
1671
1673
2825
5513
10761
21001
41737
41735
43271
86279
45191
45319
82311
45319
86471
156295
303751
305799
306183
318471
159623
318471
615687
1161223
2235919
2236431
4406799
4439567
4431375
8855567
17447951
34883599
35411983
70293519
14055015...

result:

ok 49924 lines

Test #24:

score: 0
Accepted
time: 16ms
memory: 11876kb

input:

2
2 1
50000
+ 1 1
+ 1 2
+ 1 2
+ 1 1
+ 1 1
+ 2 2
+ 2 2
+ 1 1
+ 1 1
+ 1 2
+ 2 2
+ 2 2
+ 2 2
+ 2 2
+ 1 2
+ 1 1
+ 1 1
+ 2 2
+ 2 2
+ 1 1
+ 1 2
+ 2 2
+ 1 2
+ 2 2
+ 2 2
+ 1 1
+ 1 1
+ 1 1
+ 1 2
+ 2 2
+ 1 1
+ 2 2
+ 2 2
+ 1 1
+ 1 1
+ 2 2
+ 1 1
+ 1 1
+ 2 2
+ 1 1
+ 1 2
+ 1 2
+ 1 2
+ 1 2
+ 2 2
+ 2 2
+ 1 1
+ 1 2
...

output:

1
3
7
15
31
35
43
75
139
279
311
375
503
759
1519
2031
3055
4079
6127
8175
16351
24543
49087
81855
147391
163775
196543
262079
524159
786303
1048447
1572735
2621311
3145599
4194175
6291327
8388479
12582783
16777087
25165695
50331391
100662783
201325567
402651135
536868863
805304319
73739768
14747953...

result:

ok 50000 lines

Test #25:

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

input:

200000
64610 125539
83705 160281
24143 45832
154846 82764
60201 126231
119699 193755
189389 133775
113877 66009
85942 34335
130076 68332
135113 173609
92701 826
135328 9849
158095 38763
138070 81324
25151 1224
88250 90383
134197 157835
145476 119887
175766 9372
132312 98062
170675 17587
184233 4903
...

output:

1
3
7
15
31
63
65
97
193
385
771
1539
3075
6151
12295
12311
12831
25135
50271
100543
100547
166083
331971
594243
595331
1185155
1185923
2235523
2497671
3026055
6050055
12098823
24157455
32583199
49434143
83136063
150244991
300191359
600087167
600104063
200190584
400368753
800737379
836720739
3736162...

result:

ok 49929 lines

Test #26:

score: 0
Accepted
time: 457ms
memory: 100264kb

input:

199969
167304 65417
4311 181236
168173 129988
105106 128180
25290 30357
7391 59851
8202 72186
141573 66876
150397 116010
136062 97012
30955 90714
27290 141690
143297 162143
82579 166833
187616 136103
177381 83739
140598 45445
33843 8765
193191 174188
164333 23706
134079 52023
55225 91918
168596 1867...

output:

1
3
5
7
15
17
25
35
55
111
191
383
463
927
1567
1695
3295
3391
6591
12671
12927
25727
48383
81151
161279
166911
303103
565247
565263
585743
586255
1164815
2321935
2322447
2326543
4464655
4474895
4491279
8767503
17534991
34967567
69177359
137596943
137961487
274276367
548413455
96556552
98653704
1112...

result:

ok 49967 lines

Test #27:

score: 0
Accepted
time: 506ms
memory: 107096kb

input:

200000
53698 117933
66256 173974
155051 150222
108377 88097
165733 1460
176632 22651
42045 84602
193837 42609
189747 21700
7674 93722
157742 75794
157398 119145
35104 140853
45711 84645
101278 149018
95798 58880
19405 131388
87737 182668
45503 140827
167401 151705
91293 118960
105734 52467
125430 75...

output:

1
3
1
2
4
3
7
9
17
25
41
57
99
131
195
291
583
967
1095
2191
2207
4399
4415
7295
4479
4991
7615
14015
22719
42175
37055
74111
148095
296063
582783
1148031
1279103
1623167
1623295
1656063
2245887
4490495
7898367
9242879
14485759
14493951
15018239
30036479
51024383
51188223
68620799
137241599
27394969...

result:

ok 49943 lines

Test #28:

score: 0
Accepted
time: 472ms
memory: 105324kb

input:

199922
107081 79120
3676 185326
84060 150979
197391 148825
189047 157345
59445 149477
184275 4094
66094 114629
90477 122338
34376 64548
124221 130428
122691 32881
145351 17012
35790 43743
35700 70460
96449 183837
187269 66576
93210 109210
55440 22006
85227 161356
156550 113505
139755 167518
165789 1...

output:

1
3
4
7
13
19
31
19
27
43
59
30
16
31
23
47
87
159
239
471
935
1479
2119
1095
2063
1487
1999
2127
2383
1767
1127
1255
627
755
1203
1335
1591
2535
3303
5639
11279
12303
14351
18447
27663
27679
32799
30751
30815
35263
22335
26623
30719
40063
50303
45695
66175
84863
89983
140159
238463
445823
298367
56...

result:

ok 49990 lines

Test #29:

score: 0
Accepted
time: 457ms
memory: 105008kb

input:

199922
154220 140933
123431 133706
26777 50582
193300 129242
144707 165894
198153 71220
138592 59306
194778 74897
3051 8956
50172 40039
106595 170361
146340 13971
26317 53384
90606 41548
132248 111371
103695 57445
194912 154378
111159 163942
31276 147729
44800 125401
20411 110815
196588 147245
10419...

output:

1
2
4
8
12
20
28
44
60
96
168
296
352
513
737
993
1985
3009
3521
3651
5699
11395
22787
28931
34051
68099
49921
31617
63233
93953
179713
295937
591873
600065
1067009
1935361
3672067
3803139
3803267
6228099
6500483
12726403
13381763
24785027
35008643
69873799
68563079
136982663
273318023
546472071
580...

result:

ok 49957 lines

Test #30:

score: 0
Accepted
time: 502ms
memory: 105508kb

input:

199979
78458 23155
161327 25592
128257 4920
165216 192902
190394 146360
10360 19392
20231 109640
25732 182433
110587 179405
86699 57912
157258 9243
96750 189064
81731 35609
165166 90771
41005 185425
166909 116598
116860 133728
187967 62078
13434 73265
87845 132491
90599 129409
97983 103399
69540 664...

output:

1
3
7
15
31
63
31
39
71
143
287
543
1087
1599
1727
3455
6911
3839
6655
12287
12295
12807
25095
25127
25191
25255
50343
100519
200967
352719
696783
836047
524719
836031
869183
870207
1738591
3475295
6752095
13504095
15601311
30805791
30806047
30805791
61214495
122032159
122560031
123615775
247231007
...

result:

ok 50000 lines

Test #31:

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

input:

200000
131423 92760
144402 47110
39734 6689
113356 123141
94650 120955
79281 168150
95682 154312
3290 130359
47546 182644
148146 17629
178901 135802
101595 76730
124702 63138
11470 106580
31734 21610
43452 20380
145832 151393
67738 190285
37182 189589
105959 134078
149602 74747
165741 79730
155266 8...

output:

1
2
4
8
16
18
20
24
40
72
76
140
73
77
73
147
283
411
561
1109
2197
4385
2192
2224
2226
4446
8546
9570
18797
19309
19461
38683
41243
82247
123295
164495
164479
82495
164511
328479
492319
984639
1837823
1971327
2102399
2757759
3680127
5654911
11291391
11290367
11293439
14439167
14439679
28876031
3202...

result:

ok 49976 lines

Test #32:

score: 0
Accepted
time: 504ms
memory: 122696kb

input:

200000
93464 176045
35518 125153
178434 38114
132184 185778
138111 30626
150503 191059
191184 126041
98518 128645
185091 155423
88828 130498
28065 177253
12397 122082
33021 132204
113560 51911
62776 64391
103313 174046
41285 6885
73434 56983
100699 178816
159437 80569
146821 188970
179065 53580
1070...

output:

1
3
7
9
15
23
39
71
127
239
479
927
991
1343
2687
4479
5887
11775
12799
15871
31743
63487
118783
135167
167935
167951
282639
565279
1130527
2146367
2080831
3113023
6226047
12255359
11108479
15827071
15827583
24216191
43090559
86180479
168166527
84083327
119734911
239469823
240126207
261097727
420481...

result:

ok 49916 lines

Test #33:

score: 0
Accepted
time: 511ms
memory: 122312kb

input:

200000
58750 185410
102499 110634
157771 194113
93740 63560
90366 11239
198691 196889
90901 16916
137845 146488
41199 120635
107218 175350
86566 16202
190752 112622
19630 149425
20809 50491
83186 93216
32204 66173
89850 33837
91609 13682
63745 5595
160462 51463
166180 191879
181359 30627
143093 1557...

output:

1
3
1
2
4
6
11
13
9
13
15
19
33
37
59
67
83
85
93
135
219
387
419
787
1403
2555
4881
9469
10173
10181
19653
39005
39037
74157
140205
148397
292845
309229
577389
634733
1257325
2316403
4436087
8826999
17634519
17700247
35382679
68954535
136882599
273658671
545895215
91681848
91814456
92342840
9234079...

result:

ok 49964 lines

Test #34:

score: 0
Accepted
time: 519ms
memory: 122008kb

input:

200000
133666 168679
119112 127822
83847 102279
78104 73830
88051 106192
151217 46601
123049 96277
151021 47059
22496 48383
100550 36087
48839 72744
93083 27609
112788 123096
157340 16616
147625 171999
53910 103999
165616 32155
78086 121124
87174 3190
97858 121272
107801 185540
131287 187431
159750 ...

output:

1
2
4
3
5
11
23
47
55
71
119
183
215
375
439
279
551
1095
839
423
743
747
748
1396
2692
2820
5480
9712
10256
10768
10832
10864
20096
22144
44032
77857
77889
155201
310017
605377
1195329
2384001
2385153
1336449
2672769
2689665
1378881
2460289
2727809
4890625
9768961
18477313
36954113
18489345
1965260...

result:

ok 50000 lines

Test #35:

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

input:

3
3 2
1 3
50000
+ 2 3
+ 3 3
+ 1 2
+ 1 1
+ 3 3
+ 3 3
+ 1 1
+ 1 3
+ 2 2
+ 3 3
+ 1 2
+ 2 2
+ 1 2
+ 2 2
+ 2 2
+ 1 2
+ 1 2
+ 2 3
+ 1 3
+ 3 3
+ 2 2
+ 1 3
+ 3 3
+ 1 3
+ 2 2
+ 1 2
+ 2 2
+ 3 3
+ 1 3
+ 1 2
+ 3 3
+ 2 2
+ 1 2
+ 2 3
+ 1 3
+ 1 1
+ 3 3
+ 3 3
+ 3 3
+ 1 3
+ 2 3
+ 1 3
+ 2 2
+ 2 2
+ 1 1
+ 1 3
+ 2 3
+ ...

output:

1
3
7
9
17
33
37
75
79
143
287
303
607
671
799
1599
3199
6207
10495
18687
20735
37503
70271
136575
140671
281343
297727
559871
1087231
2174463
4271615
4337151
8674303
17324031
34125823
34191359
67745791
134854655
269072383
537622527
75015672
148986865
150035441
152132593
152656881
301123555
60028103...

result:

ok 50000 lines

Test #36:

score: 0
Accepted
time: 504ms
memory: 123124kb

input:

199994
36840 95135
129865 112251
101798 187774
14361 37008
55756 143530
46420 10936
191075 30027
14790 111279
188509 131410
67632 158004
161290 95558
33354 184015
153434 28737
120715 156963
41475 67538
76849 165125
84528 133034
26887 147086
107379 167253
191021 176690
137738 15327
81712 85451
105632...

output:

1
3
7
9
13
17
19
39
59
75
147
151
219
267
531
723
1175
1239
1495
2271
2783
3823
7647
8031
14943
29823
47231
93311
113791
125055
146623
232703
432511
864767
1565439
2999295
5997567
5997695
11338879
13960831
27921663
54529279
109058559
159390207
301996543
317463039
384571903
769143295
769180159
511571...

result:

ok 49999 lines

Test #37:

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

input:

199986
44484 88033
170763 105703
12052 15210
190682 3734
145537 55731
26309 75415
9754 163115
120925 174031
143835 44064
108502 155133
124880 77386
35705 96348
13158 30865
198214 130710
112779 59176
133450 29375
173445 142656
145480 5526
195745 105013
191262 146057
102105 172477
5524 56587
187688 67...

output:

1
3
5
9
19
27
31
47
91
179
307
615
655
1311
1135
2271
2367
4607
5375
10239
18431
18943
18947
23043
11779
12419
6659
7171
7427
14211
24963
35331
57863
66567
87055
168991
175135
350239
579647
1159231
643135
1011775
1830975
3530815
3948607
7716927
13221951
26443839
51707967
52494399
52592703
52756543
1...

result:

ok 49935 lines

Test #38:

score: 0
Accepted
time: 521ms
memory: 124252kb

input:

199972
149584 42693
76362 49467
159038 49395
44882 74291
93306 101070
93733 115544
4575 75791
148735 72413
52295 152497
8417 85198
86901 57115
116032 36187
15637 102061
76801 49118
40864 111559
102517 58069
36985 58063
187123 152686
48022 2108
80569 82216
48854 12046
136801 144587
53750 117438
11649...

output:

1
3
5
9
5
2
5
11
12
24
40
72
145
153
179
359
679
711
879
1727
3263
2559
2567
4647
9295
9327
10831
21519
22031
44047
77071
80655
160783
161807
81415
94727
162567
324103
644615
777735
1554447
865807
865815
1390615
2780207
3238959
6474815
10882111
10886207
10894431
21787807
43574431
43558047
21930655
4...

result:

ok 50000 lines

Test #39:

score: 0
Accepted
time: 518ms
memory: 122996kb

input:

199960
66674 111218
60472 126836
112058 72024
53650 50961
133801 160785
104450 23301
199211 36411
142414 114723
127074 113631
10195 33573
102303 47087
31978 27788
155288 92753
102734 46245
197327 139719
93627 196008
190639 196187
171833 155974
97160 6948
13917 193576
166533 151078
70620 144489
68976...

output:

1
2
4
8
17
35
67
131
195
323
643
655
911
1823
1887
3775
7391
7407
14703
22895
23983
27215
27983
44367
47519
88479
92575
92703
180895
324511
324543
353215
706175
706687
837759
1624191
2854079
5050303
9508799
9510847
19017983
20329343
40653695
40720255
41836671
41836703
77750431
148021407
148022431
14...

result:

ok 49983 lines

Test #40:

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

input:

200000
163387 94400
130365 31392
174420 57560
103105 32878
96595 10564
90097 179557
162011 107745
193662 192972
80073 198975
24026 178154
14362 20437
15559 36902
155321 19505
81151 80049
192912 134867
155410 21396
21445 99997
46433 113144
10486 89572
85233 144920
120692 10151
37988 122772
90110 6969...

output:

1
2
4
2
4
3
7
3
1
3
7
3
7
15
31
15
31
15
7
3
1
0
1
0
1
3
1
3
7
11
23
39
71
87
55
39
79
39
19
23
17
21
43
75
139
183
215
183
367
735
1375
2399
2095
1071
2143
1119
1055
2079
4127
8255
16447
8255
8259
4163
8263
4163
2115
1059
2115
2147
4195
8295
8311
16519
18631
10419
10291
20563
12369
24659
12363
8267...

result:

ok 49994 lines

Test #41:

score: 0
Accepted
time: 322ms
memory: 60704kb

input:

199946
11967 40196
114587 61975
103751 60735
178039 109154
12518 59533
146422 133138
106386 38649
104155 126399
31899 50912
110951 183773
115832 118367
135065 20533
158350 63600
57717 44063
102917 95997
183849 42677
71877 148923
88305 154146
113193 153271
192551 53235
124542 21766
127440 107238
2281...

output:

1
2
1
2
3
2
1
3
5
9
4
3
1
3
1
3
1
0
1
3
5
9
17
35
43
87
119
191
159
303
559
1103
551
679
339
595
307
595
591
527
783
1567
1695
1823
911
913
923
939
475
499
255
159
183
323
427
811
619
603
365
717
365
461
923
1179
923
919
791
1583
1071
1903
1887
3743
3807
4031
4543
4547
4419
8835
4419
4259
4295
2167
...

result:

ok 50000 lines

Test #42:

score: 0
Accepted
time: 371ms
memory: 99424kb

input:

200000
133972 109486
8068 182579
171264 91251
164605 12251
176542 79672
76644 83254
113978 154294
153753 134144
24328 64385
139999 13474
68006 154017
12511 40582
31107 36891
68316 131489
51534 61164
100735 109836
133530 159486
148250 38750
114387 163081
123918 21938
189321 126743
120406 173986
83822...

output:

1
3
1
3
1
2
5
6
4
3
1
0
1
2
1
0
1
2
1
0
1
0
1
0
1
0
1
3
7
15
31
39
23
39
19
11
19
11
19
21
19
27
29
57
89
179
211
105
115
155
307
387
515
403
369
739
643
387
195
231
191
175
183
91
73
69
37
33
17
15
7
15
17
9
11
23
43
44
34
44
28
18
17
33
67
35
71
39
55
71
135
67
35
43
75
77
85
77
85
53
41
69
39
77
...

result:

ok 50000 lines

Test #43:

score: 0
Accepted
time: 413ms
memory: 105928kb

input:

200000
135285 86406
193685 187759
28813 126955
119609 188194
6960 136819
172807 154864
797 157733
7023 43617
66713 125717
107689 152403
28264 184813
5265 17027
174774 115075
153438 198251
119793 125620
123733 22993
166544 25623
4615 49051
68418 10418
84661 158854
158406 12775
178172 187097
198020 10...

output:

1
0
1
0
1
0
1
2
3
2
1
0
1
0
1
3
7
3
7
15
31
15
16
15
7
15
7
3
7
3
1
0
1
0
1
0
1
3
1
0
1
0
1
0
1
3
1
0
1
2
4
3
1
2
4
6
13
23
31
55
29
25
41
57
97
49
33
25
12
21
11
13
17
29
27
43
35
21
13
15
29
15
9
7
13
27
23
11
19
11
5
9
11
6
8
6
9
7
11
9
17
9
5
3
7
15
31
47
31
63
95
191
95
191
95
191
383
639
1279
...

result:

ok 50000 lines

Test #44:

score: 0
Accepted
time: 434ms
memory: 122288kb

input:

199930
48074 80810
36504 118301
102740 194889
47992 57694
106856 55982
43440 69176
29678 49687
17641 83699
79431 129872
58616 52099
162746 123014
143502 130653
110321 40999
54066 25929
71458 8206
7442 144249
199397 15138
197497 43237
28469 7986
69517 187498
20654 129661
173261 198769
142327 61670
14...

output:

1
3
7
9
19
39
79
159
319
255
127
63
127
63
31
15
7
15
7
3
7
11
15
19
15
31
47
35
67
71
139
271
263
135
263
135
271
335
463
231
295
195
323
343
183
359
719
1439
2847
3103
5951
3519
4287
3263
3135
6207
6463
5311
3775
2751
5375
7423
3775
4287
6847
4287
2175
1119
2175
3007
4799
3007
4031
6143
6399
6143
...

result:

ok 50000 lines

Test #45:

score: 0
Accepted
time: 442ms
memory: 123712kb

input:

200000
122932 140125
129341 182866
46556 79821
170528 55257
53720 51334
19830 45347
92313 113207
64552 158918
134182 155406
178215 136008
186506 49934
51621 135241
2637 110247
14678 115257
99908 9909
8606 28054
32110 192058
18184 2997
150768 37295
105940 79278
37717 169431
68087 89059
134829 85959
2...

output:

1
0
1
2
1
0
1
0
1
3
1
0
1
0
1
0
1
0
1
2
1
2
1
0
1
2
1
0
1
0
1
0
1
0
1
3
7
11
7
11
5
3
1
3
1
3
4
3
1
3
1
3
1
0
1
2
1
3
7
3
1
2
4
3
7
11
5
11
7
3
1
0
1
0
1
0
1
3
1
0
1
0
1
0
1
0
1
0
1
3
7
9
13
14
10
6
5
3
5
3
5
3
5
11
19
11
5
2
1
3
1
3
7
9
5
2
1
0
1
0
1
2
1
0
1
0
1
0
1
0
1
3
7
15
19
9
5
2
4
2
1
2
1
0
...

result:

ok 49996 lines

Test #46:

score: 0
Accepted
time: 17ms
memory: 11756kb

input:

4
4 1
1 3
2 1
50000
+ 2 3
+ 4 4
+ 4 4
+ 1 4
+ 1 4
+ 2 3
+ 1 3
+ 1 3
+ 3 4
+ 1 3
+ 1 4
+ 1 1
+ 2 4
+ 2 4
+ 1 2
+ 1 3
+ 1 4
+ 2 4
+ 3 3
+ 2 2
+ 1 2
+ 3 3
+ 2 2
+ 1 3
+ 2 4
+ 2 3
+ 2 2
+ 2 3
+ 3 3
+ 1 3
+ 1 3
+ 1 3
+ 2 2
+ 1 4
+ 2 3
+ 1 3
+ 3 4
+ 2 2
+ 2 4
+ 4 4
+ 1 3
+ 1 4
+ 4 4
+ 1 2
+ 3 4
+ 3 3
+ 2 ...

output:

1
2
4
9
19
27
43
75
151
279
559
1071
2143
4287
8383
16575
33151
66303
66431
66495
132095
132351
132607
264063
527359
1053183
1055231
2108927
2113023
4217343
8425983
16843263
16851455
33630207
67257343
134480895
268931071
268963839
537468927
537485311
74814968
148585457
148650993
296261603
592269255
...

result:

ok 50000 lines

Test #47:

score: 0
Accepted
time: 441ms
memory: 123576kb

input:

200000
189404 73188
94395 54404
11733 110279
181147 41399
11204 163094
64526 16888
136513 198440
183267 194176
6950 25635
175375 64342
189554 144823
164155 8485
102824 82381
130681 50110
193807 161933
116079 172036
78548 185573
65460 8842
179536 112172
47040 97785
112638 168042
103138 142049
118536 ...

output:

1
0
1
0
1
0
1
0
1
0
1
0
1
3
1
3
1
3
1
0
1
0
1
3
7
11
19
31
15
23
15
7
8
17
8
5
3
2
1
2
3
2
1
0
1
2
5
9
17
15
7
3
1
3
1
2
5
3
1
0
1
0
1
0
1
2
4
2
3
6
7
5
3
5
3
2
4
6
7
12
8
15
23
31
61
45
73
123
107
59
31
27
43
87
167
159
319
191
223
127
63
95
175
239
351
175
335
351
255
479
239
119
85
165
173
333
66...

result:

ok 50000 lines

Test #48:

score: 0
Accepted
time: 509ms
memory: 139160kb

input:

200000
77504 150136
149029 100126
79630 152786
59741 36581
142342 154069
197187 16668
54154 180361
115847 164757
122071 198863
65801 149813
11733 120875
44374 112671
21400 138274
143662 21212
191706 63110
6236 152126
99016 97732
79026 187141
117803 84677
99898 30517
89769 102382
55638 20267
11434 13...

output:

1
3
7
11
19
35
71
143
271
543
1087
2111
4159
8319
8327
16655
17167
22031
44047
76831
142367
284703
323615
647231
1294463
2588799
4685951
9371775
10616959
11141247
14155903
14157951
20187263
24383615
32772223
65544319
131080447
164634879
329269759
463487487
926974975
463878648
927691761
464564714
612...

result:

ok 50000 lines

Test #49:

score: 0
Accepted
time: 351ms
memory: 60428kb

input:

200000
122019 98771
118577 111790
106704 118678
177418 168810
194976 164789
31289 199544
70813 177000
58395 124876
77214 93965
19556 80774
61898 147269
105655 131685
83150 89692
175727 112770
116783 56312
189933 71031
120984 31638
140197 108867
55097 33350
32179 138234
127312 52428
71319 44011
15327...

output:

1
3
7
15
31
63
127
143
287
575
577
1089
1093
2185
2441
2953
5907
6163
6291
6547
7571
15123
29731
49699
77379
154691
161859
321667
321795
641411
641475
645703
907847
1776199
3552399
7104655
14208159
27628703
28255423
56509695
56510719
59001087
113004927
117199231
229400959
279732607
281829759
3874737...

result:

ok 50000 lines

Test #50:

score: 0
Accepted
time: 446ms
memory: 105612kb

input:

200000
86460 127915
164559 85215
88871 130138
133323 175625
106579 168398
79795 62863
1092 71833
180868 185053
169498 190742
135255 45630
59395 58051
115559 194976
143570 36656
144275 195207
187593 44810
136612 188073
61988 64547
154433 102694
112338 111870
15258 70873
30817 63402
60800 94273
14553 ...

output:

1
2
3
7
9
17
29
45
47
89
179
207
407
807
935
1775
1776
2256
2304
4288
7872
8705
8833
14017
25409
45889
46401
58689
111937
223873
446593
450689
712833
1423489
2242689
2242817
4483585
8894977
17746433
35449345
36776961
38917121
64082945
66737153
66741249
128697345
252609537
282305537
283108353
3600476...

result:

ok 50000 lines

Test #51:

score: 0
Accepted
time: 460ms
memory: 122300kb

input:

200000
167885 110
170987 33868
121388 141172
112843 4047
47096 178346
192149 74520
163904 148077
42019 197927
187109 154268
134330 152148
122580 93323
94026 74679
91129 49079
14924 132590
190679 138438
20678 76905
93943 186082
115515 181230
42418 98010
63147 166362
48174 26646
42722 66007
96659 2245...

output:

1
2
4
9
17
19
23
25
45
61
93
187
255
383
415
823
1607
2631
5231
5359
6063
6111
8543
10079
14175
16559
16703
32703
49727
97119
98655
194911
266079
267167
406431
409119
445983
474943
696127
696383
1392191
2014783
4014143
6832191
11682943
15761023
31518335
63033983
125948543
130142847
130143359
1994312...

result:

ok 50000 lines

Test #52:

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

input:

200000
119333 139147
130394 5613
35775 148679
130904 46270
28230 107747
5969 57625
177449 30191
49545 196340
119443 79272
4198 107975
98434 179900
167689 31071
175918 32664
130997 78379
111386 149604
193645 48716
174280 144964
66719 127197
97462 66002
30848 156592
161511 185455
109297 186651
53080 5...

output:

1
2
4
7
8
14
16
26
42
52
60
116
189
205
411
787
1331
1603
3107
6179
12227
13379
13639
27271
31495
62991
119311
120335
121359
126991
183311
193551
275471
341007
519183
1022991
2030607
3017743
5884943
11769887
11770399
19241503
19249695
19282463
38384159
64254495
64385567
64385631
64388287
110459263
2...

result:

ok 50000 lines

Test #53:

score: 0
Accepted
time: 24ms
memory: 11788kb

input:

4
3 1
2 1
2 4
50000
+ 1 4
+ 1 2
+ 2 2
- 1 4
- 2 2
+ 1 1
- 1 1
+ 1 1
- 1 2
+ 3 3
+ 1 1
+ 4 4
- 4 4
+ 1 2
+ 3 4
+ 3 4
+ 2 2
+ 2 2
+ 1 3
+ 2 4
+ 2 4
+ 3 3
+ 4 4
- 2 4
+ 2 2
+ 4 4
- 2 2
+ 1 3
+ 1 3
+ 1 4
+ 2 4
- 3 3
+ 3 4
+ 2 3
+ 2 2
+ 3 4
+ 3 4
+ 1 3
+ 1 3
+ 1 2
+ 2 3
+ 2 4
+ 1 4
- 1 1
+ 1 3
+ 1 3
+ 1 ...

output:

1
3
7
3
1
3
1
3
1
2
4
5
4
8
17
35
43
59
95
127
191
207
223
151
215
231
167
255
431
767
943
879
1759
3327
4351
8703
17407
26111
43519
84223
167679
201215
398335
267263
402431
672767
1197055
598527
1122815
2237439
2371583
2387967
4509695
4777983
9506815
9539583
10645503
10776575
11038719
11563007
1051...

result:

ok 50000 lines

Test #54:

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

input:

1000
547 681
16 241
623 782
14 286
855 917
613 756
854 333
84 40
343 353
63 106
180 482
768 578
299 180
582 238
998 699
766 455
114 282
206 786
151 844
841 317
409 705
560 387
872 441
290 501
457 954
36 807
267 167
608 99
244 857
696 787
56 452
327 735
684 125
193 772
308 237
180 923
735 701
236 599...

output:

1
3
7
15
16
32
16
32
16
8
7
15
31
63
31
15
7
3
1
2
4
6
5
9
17
35
19
35
67
131
195
323
643
1159
2183
4359
8711
8839
9871
10399
20127
24735
48287
95391
95647
95391
186655
322079
584735
1168447
635455
1168447
1168455
2218055
4333639
8630407
17248391
34095239
34357383
34373767
68321415
136609927
2731952...

result:

ok 1000 lines

Test #55:

score: 0
Accepted
time: 71ms
memory: 60968kb

input:

200000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 5...

output:

1
3
7
15
31
63
127
255
511
1023
2047
4095
8191
16383
32767
65535
131071
262143
524287
1048575
2097151
4194303
8388607
16777215
33554431
67108863
134217727
268435455
536870911
73741816
147483633
294967267
589934535
179869064
359738129
719476259
438952512
877905025
755810044
511620082
23240158
4648031...

result:

ok 5274 lines

Test #56:

score: 0
Accepted
time: 311ms
memory: 90676kb

input:

131072
105377 37060
95043 77702
24584 127218
26744 64395
66155 38930
60080 31888
30279 4795
87959 39534
84508 1854
114595 28824
2809 19036
94900 54211
54180 13413
5652 99859
104245 100479
14170 79895
118224 7206
62548 125572
81252 48406
120877 84357
85666 66171
23230 2186
38143 6930
2400 4937
99863 ...

output:

1
2
5
11
23
25
49
81
163
323
387
388
420
676
677
673
1345
2369
4545
9089
18049
35969
71937
137473
137985
275969
550402
1100802
2149378
4298754
4370436
4370500
8728648
17444944
17449040
34898000
18120752
18120768
36216896
18128952
9064504
9080888
9080890
17477722
34271386
67858586
135651482
271180066...

result:

ok 45080 lines

Extra Test:

score: 0
Extra Test Passed