QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#723965#7608. CliquesinksamuraiAC ✓1996ms78288kbC++2315.8kb2024-11-08 05:10:082024-11-08 05:10:09

Judging History

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

  • [2024-11-08 05:10:09]
  • 评测
  • 测评结果:AC
  • 用时:1996ms
  • 内存:78288kb
  • [2024-11-08 05:10:08]
  • 提交

answer

#include <bits/stdc++.h>

// cut here
namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder

namespace atcoder {

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
  public:
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder
// cut here

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define vec(...) vector<__VA_ARGS__>
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

// yosupo Vertex Add Path Sum parentheses
//   <https://judge.yosupo.jp/submission/72507>
// References:
//   <https://cp-algorithms.com/graph/hld.html>
//   <https://codeforces.com/blog/entry/53170>
//   <https://ei1333.github.io/luzhiled/snippets/tree/heavy-light-decomposition.html>
//   <https://atcoder.jp/contests/past202010-open/submissions/21473312>
//   <https://math314.hateblo.jp/entry/2014/06/24/220107>
//   <https://qiita.com/Pro_ktmr/items/4e1e051ea0561772afa3>

// HL 分解 (Heavy Light Decomposition)
//   - 頂点に (単位元ではない) 初期値を与える場合の注意点
//     - hld.build() の実行後に行う
//     - 頂点 u は hld 内部では hld.in[u] となることに注意
//   - 辺に値がある場合は子側の頂点に持たせて edge = true で関数を呼び出す
struct HLD {
    int N, root;
    vector<vector<int>> G;
    vector<int> parent;  // 頂点 u の親
    vector<int> depth;  // 頂点 u の深さ
    vector<int> sz;  // 頂点 u を根とする部分木のサイズ (heavy)
    vector<int> in;  // HL 分解時の探索順序 (Euler Tour)
    vector<int> out;  // 後述
    vector<int> head;  // 頂点 u が属する HL 分解後の連結成分の根
    vector<int> rev;  // 探索順序番号から元の頂点番号への逆引き
    int t = 0;  // 探索順序の計算用

    // [ in[u], out[u] )      := 頂点 u を根とする部分木に対応
    // [ in[head[u]], in[u] ] := HL 分解後の連結成分における頂点 u からその head までのパスに対応

    HLD() {}
    HLD(int n, int r = 0) : N(n), root(r) {
        G.resize(N); parent.resize(N); depth.resize(N); sz.resize(N);
        in.resize(N); out.resize(N); head.resize(N); rev.resize(N);
    }

    // 双方向に辺を張る
    void add_edge(int u, int v) {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    // 各部分木のサイズを求める
    void dfs_sz(int u, int p, int d) {
        parent[u] = p;
        depth[u] = d;
        sz[u] = 1;
        // heavy edge が先頭に来るように維持しながら探索する
        if (G[u].size() && G[u][0] == p) swap(G[u][0], G[u].back());
        for (int& v : G[u]) if (v != p) {  // NOTE: swap のために int& が必要
            dfs_sz(v, u, d + 1);
            sz[u] += sz[v];
            if (sz[G[u][0]] < sz[v]) swap(G[u][0], v);
        }
    }

    // HL 分解 (Heavy Light Decomposition)
    void dfs_hld(int u, int p) {
        in[u] = t++;
        rev[in[u]] = u;
        for (const int& v : G[u]) if (v != p) {
            head[v] = (v == G[u][0] ? head[u] : v);  // heavy or light
            dfs_hld(v, u);
        }
        out[u] = t;
    }

    void build() {
        dfs_sz(root, -1, 0);
        dfs_hld(root, -1);
    }

    // 頂点 u から深さ d だけ親を辿る (level-ancestor) : O(log N)
    // 辿った先が木上にあることを想定している
    //   - d <= depth[u]
    int la(int u, int d) const {
        assert(0 <= u && u < N);
        while (true) {
            int v = head[u];
            if (in[u] - d >= in[v]) return rev[in[u] - d];
            d -= in[u] - in[v] + 1;
            u = parent[v];
        }
    }

    // 頂点 u, v の LCA : O(log N)
    int lca(int u, int v) const {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        while (true) {
            if (in[u] > in[v]) swap(u, v);  // in[u] <= in[v]  (u が根側)
            if (head[u] == head[v]) return u;
            v = parent[head[v]];
        }
    }

    // (u, v) パス間の辺数 : O(log N)
    int distance(int u, int v) const {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        return depth[u] + depth[v] - 2*depth[lca(u, v)];
    }

    // 頂点 w が (u, v) パス上に存在するか : O(log N)
    bool on_path(int u, int v, int w) const {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        assert(0 <= w && w < N);
        return distance(u, w) + distance(w, v) == distance(u, v);
    }

    // パス [u,v] に対する更新クエリ : O((log N)^2)
    template<class F>
    void apply_path(int u, int v, bool edge, const F& func) {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        while (true) {
            if (in[u] > in[v]) swap(u, v);  // in[u] <= in[v]  (u が根側)
            if (head[u] == head[v]) break;
            func(in[head[v]], in[v]);
            v = parent[head[v]];
        }
        func(in[u] + edge, in[v]);
    }

    // パス [u,v] に対する取得クエリ : O((log N)^2)
    template <class S, S (*op)(S, S), S (*e)(), class F>
    S prod_path(int u, int v, bool edge, const F& func) const {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        S Su = e(), Sv = e();
        while (true) {
            if (in[u] > in[v]) { swap(u, v); swap(Su, Sv); }  // in[u] <= in[v]  (u が根側)
            if (head[u] == head[v]) break;
            Sv = op(Sv, func(in[head[v]], in[v]));
            v = parent[head[v]];
        }
        return op(Su, op(Sv, func(in[u] + edge, in[v])));
    }

    // 頂点 u を根とする部分木に対する更新クエリ : O(log N)
    void apply_subtree(int u, bool edge, function<void(int, int)> func) {
        assert(0 <= u && u < N);
        func(in[u] + edge, out[u] - 1);
    }

    // 頂点 u を根とする部分木に対する取得クエリ : O(log N)
    template <class S>
    S prod_subtree(int u, bool edge, function<S(int, int)> func) const {
        assert(0 <= u && u < N);
        return func(in[u] + edge, out[u] - 1);
    }
};

// snuke's mod int
template <ll mod>
struct modint{
	ll x;
	modint(ll x=0):x((x%mod+mod)%mod){}
	modint operator-()const{return modint(-x);}
	modint& operator+=(const modint a){if((x+=a.x)>=mod) x-=mod; return *this;}
	modint& operator-=(const modint a){if((x+=mod-a.x)>=mod) x-=mod; return *this;}
	modint& operator*=(const modint a){(x*=a.x)%=mod; return *this;}
	modint operator+(const modint a)const{modint res(*this); return res+=a;}
	modint operator-(const modint a)const{modint res(*this); return res-=a;}
	modint operator*(const modint a)const{modint res(*this); return res*=a;}
	modint pow(ll n)const{
		modint res=1,x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modint inv()const{return pow(mod-2);}
};

using mint=modint<1000000007>;

typedef vec(mint) vm;

mint op(mint l,mint r){
	return l+r;
}

mint e(){
	return 0;
}

mint mapping(mint l,mint r){
	return l*r;
}

mint composition(mint l,mint r){
	return l*r;
}

mint id(){
	return 1;
}

void slv(){
	int n;
	cin>>n;

	vec(vi) adj(n);
	HLD hld(n,0);
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		u-=1,v-=1;
		hld.add_edge(u,v);
		adj[u].pb(v),adj[v].pb(u);
	}
	hld.build();
	bool edge=0;

	vi par(n),dep(n),tin(n),tout(n);
	int _tm=0;
	auto dfs=[&](auto self,int v)->void{
		tin[v]=_tm++;
		for(auto u:adj[v]){
			if(u==par[v]) continue;
			par[u]=v;
			dep[u]=dep[v]+1;
			self(self,u);
		}
		tout[v]=_tm;
	};
	dfs(dfs,0);

	vec(vi) spr(20,vi(n));
	{
		rep(v,n){
			spr[0][v]=par[v];
		}	
		rng(j,1,20){
			rep(v,n){
				spr[j][v]=spr[j-1][spr[j-1][v]];
			}
		}
	}

	auto is_ancestor=[&](int u,int v){
		return tin[u]<=tin[v] and tin[v]<tout[u];
	};

	auto lca=[&](int u,int v)->int{
		if(is_ancestor(u,v)) return u;
		if(is_ancestor(v,u)) return v;
		per(j,20){
			if(!is_ancestor(spr[j][u],v)){
				u=spr[j][u];
			}
		}
		return par[u];
	};
	// print(lca(3,5));

	auto shift=[&](int u,int d)->int{
		per(j,20){
			if(d>>j&1){
				u=spr[j][u];
			}
		}
		return u;
	};

	vec(mint) x(n);
	rep(v,n){
		x[hld.in[v]]=1;
	}
	atcoder::lazy_segtree<mint,op,e,mint,mapping,composition,id> a(x),b(x);

	auto get=[&](int u,int up)->mint{
		mint res=0;
		// while(x!=up){
		// 	res+=a[x];
		// 	res-=b[x];
		// 	x=par[x];
		// }
		if(u==up) return res;
		int d=hld.distance(u,up);
		d-=1;
		int dup=shift(u,d);
		// print(u,dup);
		res+=hld.prod_path<mint,op,e>(u, dup, edge, [&](int l, int r) {
			return a.prod(l, r+1);
		});
		res-=hld.prod_path<mint,op,e>(u, dup, edge, [&](int l, int r) {
			return b.prod(l, r+1);
		});
		return res;
	};

	mint inv2=mint(2).inv();
	auto update=[&](int u,int up,int ad){
		if(u==up) return;
		int d=hld.distance(u,up);
		d-=1;
		int dup=shift(u,d);
		hld.apply_path(u, dup, edge, [&](int l, [[maybe_unused]] int r) {
			// seg.set(l, seg.get(l) + x);
			a.apply(l,r+1,ad==1?2:inv2);
		});
		hld.apply_path(u, dup, edge, [&](int l, [[maybe_unused]] int r) {
			// seg.set(l, seg.get(l) + x);
			b.apply(l,r+1,ad==1?2:inv2);
		});
		// while(x!=up){
		// 	if(ad==1){
		// 		a[x]*=2;
		// 		b[x]*=2;
		// 	}else{
		// 		a[x]*=inv2;
		// 		b[x]*=inv2;
		// 	}
		// 	x=par[x];
		// }
	};

	int q;
	cin>>q;
	mint now=0;
	rep(i,q){
		char ch;
		cin>>ch;
		int x,y;
		cin>>x>>y;
		x-=1,y-=1;
		int up=lca(x,y);
		if(ch=='+'){
			mint val=get(x,up)+get(y,up);
			// if(i==5) print("e",val.x,up);
			{
				val+=hld.prod_path<mint,op,e>(up, up, edge, [&](int l, int r) {
					return a.prod(l, r+1);
				});
			}
			now+=val;
			update(x,up,1);
			update(y,up,1);
			{
				hld.apply_path(up, up, edge, [&](int l, [[maybe_unused]] int r) {
					// seg.set(l, seg.get(l) + x);
					a.apply(l,r+1,2);
				});
			}
		}else{
			update(x,up,-1);
			update(y,up,-1);
			{
				hld.apply_path(up, up, edge, [&](int l, [[maybe_unused]] int r) {
					// seg.set(l, seg.get(l) + x);
					a.apply(l,r+1,inv2);
				});
			}
			mint val=get(x,up)+get(y,up);
			{
				val+=hld.prod_path<mint,op,e>(up, up, edge, [&](int l, int r) {
					return a.prod(l, r+1);
				});
			}
			now-=val;
		}
		print(now.x);
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	int t;
	// cin>>t;
	t=1;
	rep(cs,t){
		slv();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0ms
memory: 3612kb

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: 281ms
memory: 46576kb

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

result:

ok 46368 lines

Test #4:

score: 0
Accepted
time: 299ms
memory: 51664kb

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 
865...

result:

ok 38380 lines

Test #5:

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

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

result:

ok 41717 lines

Test #6:

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

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 
12075...

result:

ok 42683 lines

Test #7:

score: 0
Accepted
time: 510ms
memory: 42012kb

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 
901119...

result:

ok 48590 lines

Test #8:

score: 0
Accepted
time: 715ms
memory: 40904kb

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

result:

ok 48889 lines

Test #9:

score: 0
Accepted
time: 1258ms
memory: 63428kb

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 
45076...

result:

ok 50000 lines

Test #10:

score: 0
Accepted
time: 1225ms
memory: 63276kb

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 
1173...

result:

ok 50000 lines

Test #11:

score: 0
Accepted
time: 1245ms
memory: 63380kb

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 
2998816...

result:

ok 50000 lines

Test #12:

score: 0
Accepted
time: 1996ms
memory: 63560kb

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

result:

ok 50000 lines

Test #13:

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

input:

2
2 1
1
+ 1 2

output:

1 

result:

ok single line: '1 '

Test #14:

score: 0
Accepted
time: 921ms
memory: 63724kb

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 
3...

result:

ok 49974 lines

Test #15:

score: 0
Accepted
time: 925ms
memory: 63816kb

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 
59779...

result:

ok 50000 lines

Test #16:

score: 0
Accepted
time: 914ms
memory: 63764kb

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

result:

ok 49970 lines

Test #17:

score: 0
Accepted
time: 874ms
memory: 63752kb

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 
21669221...

result:

ok 50000 lines

Test #18:

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

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 
2...

result:

ok 49942 lines

Test #19:

score: 0
Accepted
time: 419ms
memory: 72920kb

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 
763...

result:

ok 49969 lines

Test #20:

score: 0
Accepted
time: 514ms
memory: 69536kb

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 
155435...

result:

ok 49937 lines

Test #21:

score: 0
Accepted
time: 452ms
memory: 69932kb

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 
7696...

result:

ok 49976 lines

Test #22:

score: 0
Accepted
time: 473ms
memory: 68896kb

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 
4987...

result:

ok 50000 lines

Test #23:

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

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 
885556...

result:

ok 49924 lines

Test #24:

score: 0
Accepted
time: 10ms
memory: 3576kb

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 
4026...

result:

ok 50000 lines

Test #25:

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

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 
2001905...

result:

ok 49929 lines

Test #26:

score: 0
Accepted
time: 492ms
memory: 68828kb

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

result:

ok 49967 lines

Test #27:

score: 0
Accepted
time: 527ms
memory: 66400kb

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 
3003647...

result:

ok 49943 lines

Test #28:

score: 0
Accepted
time: 522ms
memory: 67796kb

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

result:

ok 49990 lines

Test #29:

score: 0
Accepted
time: 543ms
memory: 67936kb

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 
698737...

result:

ok 49957 lines

Test #30:

score: 0
Accepted
time: 580ms
memory: 65172kb

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 
61214...

result:

ok 50000 lines

Test #31:

score: 0
Accepted
time: 605ms
memory: 65792kb

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

result:

ok 49976 lines

Test #32:

score: 0
Accepted
time: 605ms
memory: 65028kb

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 
1197...

result:

ok 49916 lines

Test #33:

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

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 
27365...

result:

ok 49964 lines

Test #34:

score: 0
Accepted
time: 648ms
memory: 64976kb

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 
4...

result:

ok 50000 lines

Test #35:

score: 0
Accepted
time: 14ms
memory: 3636kb

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 
150035...

result:

ok 50000 lines

Test #36:

score: 0
Accepted
time: 646ms
memory: 64544kb

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 
3...

result:

ok 49999 lines

Test #37:

score: 0
Accepted
time: 645ms
memory: 64876kb

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

result:

ok 49935 lines

Test #38:

score: 0
Accepted
time: 676ms
memory: 64264kb

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 
1088620...

result:

ok 50000 lines

Test #39:

score: 0
Accepted
time: 661ms
memory: 64500kb

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 
41836...

result:

ok 49983 lines

Test #40:

score: 0
Accepted
time: 811ms
memory: 63804kb

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 
214...

result:

ok 49994 lines

Test #41:

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

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 
10...

result:

ok 50000 lines

Test #42:

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

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 
3...

result:

ok 50000 lines

Test #43:

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

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

result:

ok 50000 lines

Test #44:

score: 0
Accepted
time: 503ms
memory: 65520kb

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 
42...

result:

ok 50000 lines

Test #45:

score: 0
Accepted
time: 567ms
memory: 64876kb

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

result:

ok 49996 lines

Test #46:

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

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

result:

ok 50000 lines

Test #47:

score: 0
Accepted
time: 601ms
memory: 64328kb

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 
4...

result:

ok 50000 lines

Test #48:

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

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 
926...

result:

ok 50000 lines

Test #49:

score: 0
Accepted
time: 353ms
memory: 77968kb

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 
1171...

result:

ok 50000 lines

Test #50:

score: 0
Accepted
time: 467ms
memory: 68804kb

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 
12...

result:

ok 50000 lines

Test #51:

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

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

result:

ok 50000 lines

Test #52:

score: 0
Accepted
time: 654ms
memory: 64364kb

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 
64...

result:

ok 50000 lines

Test #53:

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

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 
95...

result:

ok 50000 lines

Test #54:

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

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 
172483...

result:

ok 1000 lines

Test #55:

score: 0
Accepted
time: 52ms
memory: 78288kb

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

result:

ok 5274 lines

Test #56:

score: 0
Accepted
time: 710ms
memory: 40984kb

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 
174...

result:

ok 45080 lines

Extra Test:

score: 0
Extra Test Passed