#include<bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)
#define ll long long
#define mod 1000000007
#define bitcount    __builtin_popcountll
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,i,j;
    string s[102];
    sd(n);
    for(i=0;i<n;i++)
    {
    	cin>>s[i];
    	for(j=0;j<i;j++)
    	{
    		if(s[i]==s[j])
    			break;
    	}
    	if(j==i)
    		printf("NO\n");
    	else
    		printf("YES\n");
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)
#define ll long long
#define mod 1000000007
#define bitcount    __builtin_popcountll
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
int a[100005];
ll dp[100005][3];
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,p,q,r,i;
    sd(n);
    sd(p);
    sd(q);
    sd(r);
    for(i=0;i<n;i++)
    	sd(a[i]);
    dp[0][0]=1ll*p*a[0];
    for(i=1;i<n;i++)
    	dp[i][0]=max(dp[i-1][0],1ll*p*a[i]);
    dp[0][1]=dp[0][0]+1ll*q*a[0];
    for(i=1;i<n;i++)
    	dp[i][1]=max(dp[i-1][1],dp[i][0]+1ll*q*a[i]);
    dp[0][2]=dp[0][1]+1ll*r*a[0];
    for(i=1;i<n;i++)
    	dp[i][2]=max(dp[i-1][2],dp[i][1]+1ll*r*a[i]);
    printf("%lld\n",dp[n-1][2]);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)
#define mod 1000000007
#define bitcount __builtin_popcountll
#define ll long long
#define pb push_back
#define pi pair<int,int>
#define pii pair<pi,int>
#define mp make_pair
int minleft[100005],minright[100005],maxleft[100005],maxright[100005],a[100005];
int main()
{
	int i,j,k;
	int n,p,q,r;
	cin>>n>>p>>q>>r;
	for(i=1;i<=n;i++)
		sd(a[i]);
	minleft[1]=maxleft[1]=a[1];
	minright[n]=maxright[n]=a[n];
	for(i=2;i<=n;i++)
	{
		minleft[i]=min(minleft[i-1],a[i]);
		maxleft[i]=max(maxleft[i-1],a[i]);
	}
	for(i=n-1;i>=1;i--)
	{
		minright[i]=min(minright[i+1],a[i]);
		maxright[i]=max(maxright[i+1],a[i]);
	}
	ll ans=-3e18;
	for(i=1;i<=n;i++)
	{
		ll leftval = (p<0) ? 1ll*minleft[i]*p : 1ll*maxleft[i]*p;
		ll rightval = (r<0) ? 1ll*minright[i]*r : 1ll*maxright[i]*r;
		ans=max(ans,leftval+rightval+1ll*q*a[i]);
	}
	cout<<ans<<endl;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)
#define ll long long
#define mod 1000000007
#define bitcount    __builtin_popcountll
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
int dp[100005][3][12],x,k,m;
int a[3][12],b[3][12];
vector <int> q[100005];
void dfs(int cur,int par)
{
	int i,j=0,l,r,temp;
	for(i=0;i<q[cur].size();i++)
	{
		if(q[cur][i]==par)
			continue;
		j=1;
		dfs(q[cur][i],cur);
	}
	if(!j)
	{
		dp[cur][0][0]=k-1;
		dp[cur][1][1]=1;
		dp[cur][2][0]=m-k;
		return;
	}
	for(i=0;i<3;i++)
	{
		for(j=0;j<=x;j++)
		{
			a[i][j]=0;
			b[i][j]=0;
		}
	}
	for(i=0;i<3;i++)
		a[i][0]=1;
	for(i=0;i<q[cur].size();i++)
	{
		if(q[cur][i]==par)
			continue;
		for(j=0;j<3;j++)
		{
			for(l=0;l<=x;l++)
			{
				for(r=0;r<=x;r++)
				{
					if(l+r>x)
						continue;
					if(j==0)
					{
						temp=dp[q[cur][i]][0][r]+dp[q[cur][i]][1][r];
						if(temp>=mod)
							temp-=mod;
						temp+=dp[q[cur][i]][2][r];
						if(temp>=mod)
							temp-=mod;
						b[j][l+r]+=(1ll*a[j][l]*temp)%mod;
						if(b[j][l+r]>=mod)
							b[j][l+r]-=mod;
					}
					else if(j==1)
					{
						b[j][l+r]+=(1ll*a[j][l]*(dp[q[cur][i]][0][r]))%mod;
						if(b[j][l+r]>=mod)
							b[j][l+r]-=mod;
					}
					else
					{
						temp=dp[q[cur][i]][0][r]+dp[q[cur][i]][2][r];
						if(temp>=mod)
							temp-=mod;
						b[j][l+r]+=(1ll*a[j][l]*temp)%mod;
						if(b[j][l+r]>=mod)
							b[j][l+r]-=mod;
					}
				}
				
			}
		}
		for(j=0;j<3;j++)
		{
			for(l=0;l<=x;l++)
			{
				a[j][l]=b[j][l];
				b[j][l]=0;
			}
		}
	}
	for(l=0;l<=x;l++)
	{
		dp[cur][0][l]=(1ll*a[0][l]*(k-1))%mod;
		if(l>=1)
			dp[cur][1][l]=a[1][l-1];
		dp[cur][2][l]=(1ll*a[2][l]*(m-k))%mod;
	}
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,i,j,ans;
    sd(n);
    sd(m);
    for(i=1;i<n;i++)
    {
    	sd(j);
    	sd(k);
    	q[j].pb(k);
    	q[k].pb(j);
    }
    sd(k);
    sd(x);
    dfs(1,0);
    ans=0;
    for(i=0;i<3;i++)
    {
    	for(j=0;j<=x;j++)
    	{
    		//printf("%d %d %d\n",i,j,dp[1][i][j]);
    		ans+=dp[1][i][j];
    		if(ans>=mod)
    			ans-=mod;
    	}
    }
    printf("%d\n",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)
#define mod 1000000007
#define bitcount __builtin_popcountll
#define ll long long
#define pb push_back
#define pi pair<int,int>
#define pii pair<pi,int>
#define mp make_pair
vector<int>v[100005],v2[100005];
int inherit[100005],comp[100005],parent[100005][25],height[100005];
int parr[100005];
int findpar(int node)
{
	return parr[node]==node ? node : parr[node]=findpar(parr[node]);
}
void dfs(int node, int par, int inh, int com)
{
	parent[node][0]=par;
	inherit[node]=inh;
	comp[node]=com;
	height[node]=height[par]+1;
	for(int i=1;i<=20;i++)
	{
		parent[node][i]=parent[parent[node][i-1]][i-1];
	}
	for(int i=0;i<v[node].size();i++)
	{
		if(v[node][i]==par)
			continue;
		if(v2[node][i]==0)
			dfs(v[node][i],node,inh+1,com);
		else
			dfs(v[node][i],node,inh,com+1);
	}
}
int findlca(int u, int v)
{
	if(height[u]>height[v])
		swap(u,v);
	for(int i=20;i>=0;i--)
	{
		if(height[parent[v][i]]>=height[u])
		{
			v=parent[v][i];
		}
	}
	if(u!=v)
	{
		for(int i=20;i>=0;i--)
		{
			if(parent[u][i]!=parent[v][i])
			{
				u=parent[u][i];
				v=parent[v][i];
			}
		}
		u=parent[u][0];
		v=parent[v][0];
	}
	return u;
}
int main()
{
	int i,j,k;
	int n,q;
	sd(n);
	for(i=1;i<=n;i++)
		parr[i]=i;
	for(i=1;i<=n;i++)
	{
		sd(j);
		sd(k);
		if(j==-1 && k==-1)
			continue;
		v[i].pb(j);
		v[j].pb(i);
		v2[i].pb(k);
		v2[j].pb(k);
		int x=findpar(i);
		int y=findpar(j);
		if(x!=y)
			parr[x]=y;
	}
	for(i=1;i<=n;i++)
	{
		if(parent[i][0]==0)
		{
			dfs(i,i,0,0);
		}
	}
	sd(q);
	while(q--)
	{
		sd(i);
		sd(j);
		sd(k);
		int x=findpar(j);
		int y=findpar(k);
		if(x!=y)
		{
			printf("NO\n");
			continue;
		}
		x=findlca(j,k);
		if(i==1)
		{
			if(x!=j || comp[k]-comp[x]!=0 || j==k)
			{
				printf("NO\n");
			}
			else
				printf("YES\n");
		}
		else
		{
			if(inherit[k]-inherit[x]!=0 || comp[j]-comp[x]!=0 || x==k)
				printf("NO\n");
			else
				printf("YES\n");
		}
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%lld",&x)
#define slld(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)
#define ll long long
#define mod 1000000007
#define bitcount    __builtin_popcountll
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
ll dp[11][2][1030][70];
ll len[12],a[100];
ll f(ll b,ll in,ll m,ll pos)
{
	if(dp[b][in][m][pos]!=-1)
		return dp[b][in][m][pos];
	if(pos==0)
	{
		if(in!=0&&m==0)
			return dp[b][in][m][pos]=1;
		else
			return dp[b][in][m][pos]=0;
		return dp[b][in][m][pos];
	}
	ll j=0;
	if(in==0)
		j+=f(b,0,m,pos-1);
	else
		j+=f(b,1,(m^1),pos-1);
	for(ll i=1;i<b;i++)
		j+=f(b,1,(m^(1<<i)),pos-1);
	dp[b][in][m][pos]=j;
	return j;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ll n,i,j,k,in;
    ll ans,l,r,m,q,b;
    k=1e18;
    memset(dp,-1,sizeof dp);
    for(i=2;i<=10;i++)
    {
    	len[i]=1;
    	j=i;
    	while(j<k)
    	{
    		len[i]++;
    		j*=i;
    	}
    	f(i,0,0,len[i]+1);
    }
    sd(q);
    while(q--)
    {
    	sd(b);
    	sd(l);
    	sd(r);
    	ans=0;
    	l--;
    	if(l)
    	{
    		j=l;
    		i=0;
    		while(j)
    		{
    			a[i]=j%b;
    			j/=b;
    			i++;
    		}
    		m=0;
    		in=0;
    		for(j=i-1;j>=0;j--)
    		{
    			for(k=0;k<a[j];k++)
    			{
    				if(k!=0)
    					in=1;
    				if(in==0)
    					ans-=dp[b][0][m][j];
    				else
    					ans-=dp[b][1][(m^(1<<k))][j];
    			}
    			if(in|a[j])
    			{
    				in=1;
    				m=(m^(1<<a[j]));
    			}
    		}
    		ans-=dp[b][in][m][0];
    	}
    	j=r;
    	i=0;
    	while(j)
    	{
    		a[i]=j%b;
    		j/=b;
    		i++;
    	}
    	in=0;
    	m=0;
		for(j=i-1;j>=0;j--)
		{
			for(k=0;k<a[j];k++)
			{
				if(k!=0)
					in=1;
				if(in==0)
					ans+=dp[b][0][m][j];
				else
					ans+=dp[b][1][(m^(1<<k))][j];
			}
			if(in|a[j])
			{
				in=1;
				m=(m^(1<<a[j]));
			}
		}
		ans+=dp[b][in][m][0];
		printf("%lld\n",ans);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)
#define mod 1000000007
#define bitcount __builtin_popcountll
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define pii pair<pi,int>
#define mp make_pair
ll ans[1000];
int upper[1000],lower[1000];
int block;
map <int,int> low[1000],up[1000];
map <int,int> vnotup[1000],vnotdown[1000];
int notboth[1000];
int minup[100005],mindown[100005];
void updateup(int i,int l,int r,int val)
{
	if(upper[i]<=val)
		return;
	//map<int,int> m;
	map<int,int> :: iterator it;
	//m.clear();
	for(int j=l;j<=r;j++)
	{
		if(minup[j]>val)
		{
			if(minup[j]==mod&&mindown[j]==mod&&upper[i]==mod&&lower[i]==mod)
			{
				notboth[i]--;
				//notdown[i]++;
				vnotdown[i][val]++;
				//notdownsum[i]+=val;
			}
			else if(minup[j]==mod&&upper[i]==mod)
			{
				//notup[i]--;
				int temp=min(lower[i],mindown[j]);
				vnotup[i][temp]--;
				if(vnotup[i][temp]==0)
					vnotup[i].erase(temp);
				//notupsum[i]-=min(lower[i],mindown[j]);
				up[i][val]++;
				low[i][temp]++;
				ans[i]+=val;
				ans[i]+=min(lower[i],mindown[j]);
			}
			else if(mindown[j]==mod&&lower[i]==mod)
			{
				int temp=min(upper[i],minup[j]);
				vnotdown[i][temp]--;
				if(vnotdown[i][temp]==0)
					vnotdown[i].erase(temp);
				vnotdown[i][val]++;
			}
			else
			{
				ans[i]+=val-min(upper[i],minup[j]);
				up[i][min(minup[j],upper[i])]--;
				up[i][val]++;
			}
			minup[j]=val;
		}
	}
}
void updatefullup(int i,int val)
{
	if(val>=upper[i])
		return;
	map <int,int> :: iterator it; 
	int n=up[i].size();
	n--;
	ll sum=0;
	int len2=0;
	for(it=vnotup[i].begin();it!=vnotup[i].end();it++)
	{
		ans[i]+=1ll*(it->fi)*(it->se)+1ll*(it->se)*val;
		len2+=it->se;
		low[i][it->fi]+=it->se;
	}
	vnotup[i].clear();
	it=vnotdown[i].upper_bound(val);
	int temp=0;
	for(it;it!=vnotdown[i].end();it++)
	{
		temp+=it->se;
	}
	it=vnotdown[i].upper_bound(val);
	vnotdown[i].erase(it,vnotdown[i].end());
	vnotdown[i][val]+=temp+notboth[i];
	notboth[i]=0;
	int len=0;
	it=up[i].upper_bound(val);
	for(it;it!=up[i].end();it++)
	{
		sum+=1ll*(it->fi)*(it->se);
		len+=it->se;
	}
	it=up[i].upper_bound(val);
	up[i].erase(it,up[i].end());
	ans[i]+=1ll*len*val-sum;
	up[i][val]+=len+len2;
	upper[i]=val;
}
void updatedown(int i,int l,int r,int val)
{
	if(lower[i]<=val)
		return;
	//map<int,int> m;
	map<int,int> :: iterator it;
	//m.clear();
	for(int j=l;j<=r;j++)
	{
		if(mindown[j]>val)
		{
			if(mindown[j]==mod&&minup[j]==mod&&upper[i]==mod&&lower[i]==mod)
			{
				notboth[i]--;
				//notup[i]++;
				//notupsum[i]+=val;
				vnotup[i][val]++;
			}
			else if(mindown[j]==mod&&lower[i]==mod)
			{
				//notdown[i]--;
				int temp=min(upper[i],minup[j]);
				vnotdown[i][temp]--;
				if(vnotdown[i][temp]==0)
					vnotdown[i].erase(temp);
				low[i][val]++;
				up[i][temp]++;
				//notdownsum[i]-=min(upper[i],minup[j]);
				ans[i]+=val;
				ans[i]+=min(upper[i],minup[j]);
			}
			else if(minup[j]==mod&&upper[i]==mod)
			{
				int temp=min(lower[i],mindown[j]);
				vnotup[i][temp]--;
				if(vnotup[i][temp]==0)
					vnotup[i].erase(temp);
				vnotup[i][val]++;
			}
			else
			{
				ans[i]+=val-min(lower[i],mindown[j]);
				low[i][min(mindown[j],lower[i])]--;
				low[i][val]++;
			}
			mindown[j]=val;
		}
	}
}
void updatefulldown(int i,int val)
{
	if(val>=lower[i])
		return;
	map <int,int> :: iterator it; 
	int n=low[i].size();
	n--;
	ll sum=0;
	int len2=0;
	for(it=vnotdown[i].begin();it!=vnotdown[i].end();it++)
	{
		ans[i]+=1ll*(it->fi)*(it->se)+1ll*(it->se)*val;
		len2+=it->se;
		up[i][it->fi]+=it->se;
	}
	vnotdown[i].clear();
	it=vnotup[i].upper_bound(val);
	int temp=0;
	for(it;it!=vnotup[i].end();it++)
	{
		temp+=it->se;
	}
	it=vnotup[i].upper_bound(val);
	vnotup[i].erase(it,vnotup[i].end());
	vnotup[i][val]+=temp+notboth[i];
	notboth[i]=0;
	int len=0;
	it=low[i].upper_bound(val);
	for(it;it!=low[i].end();it++)
	{
		sum+=1ll*(it->fi)*(it->se);
		len+=it->se;
	}
	it=low[i].upper_bound(val);
	low[i].erase(it,low[i].end());
	ans[i]+=1ll*len*val-sum;
	low[i][val]+=len+len2;
	lower[i]=val;
}
ll query(int i,int l,int r)
{
	ll sum=0;
	for(int j=l;j<=r;j++)
	{
		if(min(upper[i],minup[j])<mod&&min(lower[i],mindown[j])<mod)
			sum+=min(upper[i],minup[j])+min(lower[i],mindown[j]);
	}
	return sum;
}
ll queryfull(int i)
{
	return ans[i];
}
int main()
{
	int i,j,k,q,n,t,l,r,val,block;
	ll s;
	n=100000;
	for(i=0;i<1000;i++)
		lower[i]=upper[i]=mod;
	for(i=0;i<=100000;i++)
		minup[i]=mindown[i]=mod;
	block=300;
	for(i=1;i<=n;i++)
	{
		j=i/block;
		notboth[j]++;
	}
	sd(q);
	while(q--)
	{
		sd(t);
		sd(l);
		sd(r);
		r--;
		if(t==1)
		{
			sd(val);
			i=l/block;
			j=r/block;
			if(val>0)
			{
				if(i==j)
					updateup(j,l,r,val);
				else
				{
					updateup(i,l,(i+1)*block-1,val);
					i++;
					while(i<j)
					{
						// updateup(i,i*block,(i+1)*block-1,val);
						updatefullup(i,val);
						i++;
					}
					updateup(j,j*block,r,val);
				}
			}
			else
			{
				if(i==j)
					updatedown(j,l,r,-val);
				else
				{
					updatedown(i,l,(i+1)*block-1,-val);
					i++;
					while(i<j)
					{
						// updatedown(i,i*block,(i+1)*block-1,-val);
						updatefulldown(i,-val);
						i++;
					}
					updatedown(j,j*block,r,-val);
				}
			}
		}
		else
		{
			s=0;
			i=l/block;
			j=r/block;
			if(i==j)
				s=query(j,l,r);
			else
			{
				s=query(i,l,(i+1)*block-1);
				i++;
				while(i<j)
				{
					//s+=query(i,i*block,(i+1)*block-1);
					s+=queryfull(i);
					i++;
				}
				s+=query(j,j*block,r);
			}
			printf("%lld\n",s);
		}
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 200005;

struct tpath
{
    int rep, sz;
    ll ansmiddle;
    int edgeleft, edgeright;
};

int p[maxn], s[maxn];
int sz[maxn], down[maxn], up[maxn], top[maxn];
vector<tpath> path, path2;
vector<int> gr[maxn];
ll dp1[maxn], dp2[maxn], ansmiddle[maxn];
int n, m;
ll answer;
int tin[maxn], tout[maxn];
int timer;

inline int find(int a)
{
    return (a == p[a] ? a : p[a] = find(p[a]));
}

inline bool isparent(int a, int b)
{
    return tin[a] <= tin[b] && tout[a] >= tin[b];
}

void unite(int a, int b)
{
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (s[a] > s[b]) swap(a, b);
    p[a] = b;
    if (s[a] == s[b]) s[b]++;
    if (tin[top[a]] < tin[top[b]])
    {
        sz[top[a]] += sz[top[b]];
        top[b] = top[a];
    } else
    {
        sz[top[b]] += sz[top[a]];
    }
}

void findpath(int a, int b)
{
    a = top[find(a)];
    b = top[find(b)];
//     cout << "findpath " << a << ' ' << b << endl;
    int lastdowna = 0;
    while (!isparent(a, b))
    {
        path.pb({a, sz[a], ansmiddle[a], lastdowna, n - down[a]});
        lastdowna = down[a];
        a = top[find(up[a])];
    }
    path2.clear();
    int lastdownb = 0;
    while (a != b)
    {
        path2.pb({b, sz[b], ansmiddle[b], n - down[b], lastdownb});
        lastdownb = down[b];
        b = top[find(up[b])];
    }
    path.pb({a, sz[a], ansmiddle[a], lastdowna, lastdownb});
    reverse(all(path2));
    for (auto t : path2) path.pb(t);
}

void addedge(int a, int b)
{
    if (find(a) == find(b)) return;
    path.clear();
    findpath(a, b);
    
//     cout << "addedge " << a << ' ' << b << endl;
//     for (auto t : path) cout << "(" << t.rep << ' ' << t.sz << ' ' << t.ansmiddle << ' ' << t.edgeleft << ' ' << t.edgeright << ")" << endl;
    
    // 3
    ll cnt0 = 1;
    ll cnt1 = 0;
    ll cnt2 = 0;
    for (auto t : path)
    {
        answer -= t.sz * cnt2 * 2 + (ll)t.sz * (t.sz - 1) * cnt1 * 2 + (ll)t.sz * (t.sz - 1) * (t.sz - 2);
        cnt2 += t.sz * cnt1 + (ll)t.sz * (t.sz - 1) * cnt0;
        cnt1 += t.sz * cnt0;
    }
    ll sum = cnt1;
    answer += ((ll)sum * (sum - 1) * (sum - 2));
    
//     cout << "after 3: " << answer << endl;
    
    // 2
    cnt1 = 0;
    for (auto t : path)
    {
        answer += cnt1 * (t.edgeleft - cnt1) * t.sz * 2;
        cnt1 += t.sz;
    }
    cnt1 = 0;
    for (int i = (int)path.size() - 1; i >= 0; i--)
    {
        auto &t = path[i];
        answer += cnt1 * (t.edgeright - cnt1) * t.sz * 2;
        cnt1 += t.sz;
    }

//     cout << "after 2: " << answer << endl;    
    
    // 1
    cnt1 = 0;
    cnt2 = 0;
    for (auto t : path)
    {
        answer += cnt2 * t.sz * 2;
        cnt2 += (n - t.edgeright - t.edgeleft - t.sz) * cnt1;
        cnt1 += n - t.edgeright - t.edgeleft - t.sz;
    }
    cnt1 = 0;
    cnt2 = 0;
    for (int i = (int)path.size() - 1; i >= 0; i--)
    {
        auto &t = path[i];
        answer += cnt2 * t.sz * 2;
        cnt2 += (n - t.edgeleft - t.edgeright - t.sz) * cnt1;
        cnt1 += n - t.edgeleft - t.edgeright - t.sz;
    }
//     cout << "after 1 old: " << answer << endl;
    ll ttldown1 = 0;
    ll ttldown2 = 0;
    for (auto t : path)
    {
        ll curdown = n - t.edgeleft - t.edgeright - t.sz;
        ll curdown2 = t.ansmiddle - curdown * (t.edgeleft + t.edgeright) * 2 - (ll)t.edgeleft * t.edgeright * 2;
        answer += curdown2 * (sum - t.sz);
        ttldown2 = ttldown2 + curdown2 + ttldown1 * curdown * 2;
        ttldown1 += curdown;
    }

//     cout << "after 1: " << answer << endl;
    
    for (int i = 1; i < (int)path.size(); i++) unite(path[i - 1].rep, path[i].rep);
    ansmiddle[top[find(path[0].rep)]] = ttldown2;
}

int go(int cur, int pr)
{
    down[cur] = 1;
    up[cur] = pr;
    dp1[cur] = 0;
    ansmiddle[cur] = 0;
    tin[cur] = timer++;
    for (auto t : gr[cur]) if (t != pr)
    {
        down[cur] += go(t, cur);
        answer += (ll)dp1[t] * dp1[cur] * 2;
        answer += (ll)dp1[t] * dp2[cur] * 2 + dp2[t] * dp1[cur] * 2;
        ansmiddle[cur] += (ll)dp1[t] * dp1[cur] * 2;
        answer += dp2[t] * 2;
        dp2[cur] += dp2[t];
        dp1[cur] += dp1[t];
    }
    ansmiddle[cur] += (ll)(n - down[cur]) * dp1[cur] * 2;
    dp2[cur] += dp1[cur];
    dp1[cur] += 1;
    tout[cur] = timer - 1;
//     cout << "exit " << cur << ' ' << answer << ' ' << dp1[cur] << ' ' << dp2[cur] << endl;
    return down[cur];
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        a--, b--;
        gr[a].pb(b);
        gr[b].pb(a);
    }
    go(0, -1);
    for (int i = 0; i < n; i++)
    {
        p[i] = i;
        s[i] = 0;
        top[i] = i;
        sz[i] = 1;
    }
    printf("%lld\n", answer);
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        a--, b--;
        addedge(a, b);
        printf("%lld\n", answer);
    }
    
    return 0;
}