//RC-u1 智能红绿灯
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
vector<pair<int,int>>  merges(vector<pair<int, int>> segs)
{
    vector<pair<int, int>> temp;
    int st = -1e9, ed = -1e9;
    sort(segs.begin(), segs.end());
    for (auto seg : segs)
    {
        if (ed < seg.first)
        {
            if (ed != -1e9) temp.push_back({ st,ed });
            st = seg.first; ed = seg.second;
        }
        else ed = max(ed, seg.second);
    }
    if (st != -1e9) temp.push_back({ st,ed });
    return temp;
}
void solve()
{
    int n;
    cin>>n;
    vector<int>t(n+1);
    vector<array<int,3>>v;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i];
    }
//  int l=t[1]+15,r=t[1]+15+30-1;
//  bool flag=0;
//  for(int i=2;i<=n;i++)
//  {
//      if(t[i]<=r&&t[i]>=l)
//      {
//          if(flag==0)
//          {
//              r+=15;
//              flag=1;
//          }
//      }
//      else 
//      {
//          if(t[i]>r)
//          {
//              flag=0;
//              if(v.empty()||v.back()!=make_pair(l,r))v.push_back({l,r});
//              l=t[i]+15;
//              r=t[i]+15+30-1;
//          }
//      }
//  }
//  v.push_back({l,r});
//  for(auto x:v)
//  {
//      cout<<x.fi<<" "<<x.se<<endl; 
//  }
    for(int i=1;i<=n;i++)
    {
        if(!v.size())
        {
            int l=t[i]+15;
            int r=l+30-1;
            v.push_back({l,r,0});
        }
        else
        {
            auto last=v.back();
//          if(t[i]<=last[1])v.pop_back();
            if(t[i]>=last[0]&&t[i]<=last[1])
            {
                if(last[2]!=1)
                {
                    //last[0]=last[1]+1;
                    last[1]=last[1]+15;
                    last[2]=1;
                    v.push_back(last);  
                }
//              else
//              {
//                  v.push_back(last);
//              }
            }
            else
            {
                if(t[i]>last[1])v.push_back({t[i]+15,t[i]+15+30-1,0});
            }
        }
    }
    sort(v.begin(),v.end());
    vector<PII>vc;
    for(auto x:v)
    {
        vc.push_back({x[0],x[1]});
    }
    vector<PII>ans=merges(vc);
//  for(int i=1;i<v.size();i++)
//  {
//      if(v[i][0]<=v[i-1][1])
//      {
//          ans.push_back({v[i-1][0],v[i][1]});
//      }   
//  } 
    for(auto x:ans)
    {
        cout<<x.fi<<" "<<x.se<<endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}
//RC-u2 女王的大敕令
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3+10;
typedef pair<int,int> PII;
int c[5], cc[5];  //上下左右
int getd(int x1, int y1, int x2, int y2){
    return abs(x1-x2)+abs(y1-y2);
}
int main(){
    int n = 5;
    for(int i = 1; i <= 4; i++)cin>>c[i];
    for(int i = 1; i <= 4; i++){
        cin>>cc[i];
        // int x = cc[i];
        // if(i==1||i==4)c[i]+=x;//上右
        // if(i==2||i==3)c[i]-=x;//下左
    }
    vector< pair<PII,PII> >vc;
    int ex, ey, d1, d2;  cin>>ex>>ey>>d1>>d2;
    for(int x1 = 1; x1 <= n; x1++){
        for(int y1 = 1; y1 <= n; y1++){
            for(int x2 = 1; x2 <= n; x2++){
                for(int y2 = 1; y2 <= n; y2++){
                    if(getd(x1,y1,x2,y2)==d1 && getd(x2,y2,ex,ey)==d2){
                        //左右攻击初始位置
                        if(x1==c[3]-cc[3] || x1==c[4]+cc[4] || y1==c[1] || y1==c[2]){
                            continue;
                        }
                        //上下攻击第一次位置
                        if(y2==c[1]+cc[1] || y2==c[2]-cc[2] || x2==c[3]-cc[3] || x2==c[4]+cc[4]){
                            continue;
                        }
                        vc.push_back({{x1,y1},{x2,y2}});
                    }
                }
            }
        }
    }
    for(auto x : vc){
        cout<<x.first.first<<" "<< x.first.second<<" "<<x.second.first<<" "<<x.second.second<<"\n";
    }
    return 0;
}
//RC-u3 战利品分配
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int maxn = 1e5+10, inf = 1e9+7;

int n, m, k, p, w[maxn];
int check(int x){ return (x>=p && (x-p)%k==0); }  //当前这步是拿得到的

vector<int>G[maxn];
int st, ed;
int dist[maxn], vis[maxn];
int dd[maxn];                          //维护到第i个点位置能拿到的最大价值
void Dijkstra(){
    for(int i = 0; i <= n; i++){dist[i] = inf; vis[i] = 0; }
    dist[st] = 1;                      //WA：因为是第i个点，不是边，所以起点要+1，（赛时1分版）
    priority_queue<PII,vector<PII>, greater<PII> > q;
    q.push({1,st});
    while(!q.empty()){
        PII t = q.top();  q.pop();
        if(vis[t.second])continue;
        vis[t.second] = 1;
        for(int to : G[t.second]){
            if(dist[to] > dist[t.second]+1){
                dist[to] = dist[t.second]+1;
                if(check(dist[to]))dd[to] = dd[t.second]+w[to];
                else dd[to] = dd[t.second];
                q.push({dist[to],to});
            }else if(dist[to] == dist[t.second]+1){
                if(dd[t.second]>dd[to]){
                    dd[to] = dd[t.second];
                    q.push({dist[to],to});
                }
            }
        }
    }
}

int main(){
    cin>>n>>m>>k>>p;
    for(int i = 1; i <= n; i++)cin>>w[i];
    for(int i = 1; i <= m; i++){
        int u,v ;  cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cin>>st>>ed;
    Dijkstra();
    if(p==1)dd[ed] += w[st];  //p==1的时候，可以多拿到一个起点的价值
    cout<<dd[ed]<<'\n';
    return 0;
}
//RC-u5 养老社区
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f,N=2e3+10,M=2*N;
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n;
int t[N];
bool st[N];
int d[N][N];
void bfs(int x)
{
    memset(st,0,sizeof st);
    queue<int>q;
    q.push(x);
    st[x]=true;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(st[j])continue;
            d[x][j]=d[x][t]+1;
            q.push(j);
            st[j]=true;
        }
    }
}
void dfs(int gen,int u,int p)
{
    if(p!=-1)d[gen][u]=d[gen][p]+1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==p)continue;
        dfs(gen,v,u);
    }
}
void solve()
{
    memset(h,-1,sizeof h);

    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            d[i][j]=1;
        }
    }
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++)cin>>t[i];
    for(int i=1;i<=n;i++)
    {
        bfs(i);
        //dfs(i,i,-1);
    }
    // for(int i=1;i<=n;i++)
 //    {
 //        for(int j=1;j<=n;j++)
 //        {
 //            cout<<d[i][j]<<" ";
 //        }
 //        cout<<endl;
 //    }
    int cnt=0;
    for(int x=1;x<=n;x++)
    {
        for(int y=x+1;y<=n;y++)
        {
            for(int z=y+1;z<=n;z++)
            {
                if(d[x][y]==d[x][z]&&d[x][y]==d[y][z])
                {
                    if(t[x]!=t[y]&&t[x]!=t[z]&&t[y]!=t[z])
                    {
                        cnt++;
                    }
                }                   
            }
        }
    }
    cout<<cnt<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}