Thiago4532

// Game - IOI'13
// Complexidade: O(n* log n)
// Thiago Mota

%:include <bits/stdc++.h>
%:define gc getchar_unlocked
using namespace std;random_device rd;mt19937 gen(rd());typedef long long ll;const int INF = 0x3f3f3f3f;typedef pair<int, int> pii;int N, M;ll mdc(ll a, ll b) <% return (b==0?a:mdc(b, a%b)); ??>inline int scan()<%	int N=0, x=gc(), s=1;	for(;x<'0'||x>'9';x=gc()) if(x=='-') s=-1;	for(;x>='0'&&x<='9';x=gc()) N = (N<<3) + (N<<1) + x-'0';	return N;??>struct Node<%	ll v, gcd;	int w;	pii key, ini, fim;	Node *l, *r;	Node(pii key, ll v): key(key), v(v), ini(key), fim(key), w(gen()), gcd(v), l(0), r(0) <%  ??>??>;inline ll gcd(Node *t) <% return (t?t->gcd:0); ??>inline void update(Node*& t)<%	if(!t) return;	t->gcd = mdc(t->v, mdc(gcd(t->l), gcd(t->r)));	t->ini = (t->l ? t->l->ini : t->key);	t->fim = (t->r ? t->r->fim : t->key);??>void merge(Node*& t, Node *l, Node *r)<%	if(!l || !r) return void(t=(l?l:r));	if(l->w >= r->w)<%		merge(l->r, l->r, r);		t = l;	??>else<%		merge(r->l, l, r->l);		t = r;	??>	updat