#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int range_rng(int l, int r)
{
return uniform_int_distribution<int>(l,r)(rng);
}
struct nava
{
int x;
int y;
char dir;
};
struct muchie
{
int to;
int cost;
};
struct nsuh
{
int a;
int b;
int when;
};
bool cmp(nsuh a, nsuh b)
{
return a.when<b.when;
}
nava ship[5005];
vector<muchie> nodes[5005];
vector<nsuh> edges;
int collided[5005];
int collision(nava a, nava b)
{
if (a.dir==b.dir)
return -1;
int diff;
if (a.dir=='E' && b.dir=='W' || a.dir=='W' && b.dir=='E')
{
if (a.dir=='W')
swap(a,b);
if (a.x==b.x && a.y<=b.y)
{
diff=b.y-a.y;
if (diff%2==0)
return diff/2;
else
return -1;
}
else
return -1;
}
if (a.dir=='S' && b.dir=='N' || a.dir=='N' && b.dir=='S')
{
if (a.dir=='N')
swap(a,b);
if (a.y==b.y && a.x<=b.x)
{
diff=b.x-a.x;
if (diff%2==0)
return diff/2;
else
return -1;
}
else
return -1;
}
if (a.dir=='E' && b.dir=='N' || a.dir=='N' && b.dir=='E')
{
if (a.dir=='N')
swap(a,b);
if (a.x<=b.x && a.y<=b.y)
{
if ((b.x-a.x)==(b.y-a.y))
return (b.x-a.x);
else
return -1;
}
else
return -1;
}
if (a.dir=='E' && b.dir=='S' || a.dir=='S' && b.dir=='E')
{
if (a.dir=='S')
swap(a,b);
if (a.x>=b.x && a.y<=b.y)
{
if ((a.x-b.x)==(b.y-a.y))
return (a.x-b.x);
else
return -1;
}
else
return -1;
}
if (a.dir=='W' && b.dir=='N' || a.dir=='N' && b.dir=='W')
{
if (a.dir=='N')
swap(a,b);
if (a.x<=b.x && a.y>=b.y)
{
if ((b.x-a.x)==(a.y-b.y))
return (b.x-a.x);
else
return -1;
}
else
return -1;
}
if (a.dir=='W' && b.dir=='S' || a.dir=='S' && b.dir=='W')
{
if (a.dir=='S')
swap(a,b);
if (a.x>=b.x && a.y>=b.y)
{
if((a.x-b.x)==(a.y-b.y))
return (a.x-b.x);
else
return -1;
}
else
return -1;
}
assert(0);
}
signed main()
{
/*
ifstream fin("arbore.in");
ofstream fout("arbore.out");
*/
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,i,j,rez,when;
cin >> n;
for (i=1; i<=n; i++)
{
cin >> ship[i].x >> ship[i].y >> ship[i].dir;
swap(ship[i].x,ship[i].y);
}
for (i=1; i<=n; i++)
{
for (j=i+1; j<=n; j++)
{
when=collision(ship[i],ship[j]);
if (when!=-1)
{
nodes[i].push_back({j,when});
nodes[j].push_back({i,when});
edges.push_back({i,j,when});
}
}
}
sort(edges.begin(),edges.end(),cmp);
for (auto x : edges)
{
if (collided[x.a]==x.when && !collided[x.b] || collided[x.b]==x.when && !collided[x.a] || !collided[x.a] && !collided[x.b])
{
collided[x.a]=x.when;
collided[x.b]=x.when;
}
}
for (i=1;i<=n;i++)
{
if (!collided[i])
cout << i << "\n";
}
return 0;
}
