Problem: A rich man has a square room with mirrors for security or just for fun. Each side of the room is eight meters wide. The floor, the ceiling and the walls are not special; however, the room can be equipped with a lot of mirrors on the walls or as vertical partitions.

Every mirror is one meter wide, as tall as the wall, double-side, perfectly reflective, and ultimately thin.

Poles to fix mirrors are located at the corners of the room, on the walls and inside the room. Their locations are the 81 lattice points at intervals of one meter. A mirror can be fixed between two poles which are one meter distant from each other. If we use the sign "+" to represent a pole, the overview of the room can be illustrated as follows.

<image>

Let us denote a location on the floor by (x,y) in a rectangular coordinate system. For example, the rectangular coordinates of the four corners of the room are (0,0), (8,0), (0,8) and (8,8), respectively. The location (x,y) is in the room if and only if the conditions 0 ≤ x ≤ 8 and 0 ≤ y ≤ 8 are satisfied. If i and j are integers satisfying the conditions 0 ≤ i ≤ 8 and 0 ≤ j ≤ 8, we can denote by (i,j) the locations of poles.

One day a thief intruded into this room possibly by breaking the ceiling. He stood at (0.75,0.25) and looked almost toward the center of the room. Precisely speaking, he looked toward the point (1, 0.5) of the same height as his eyes. So what did he see in the center of his sight? He would have seen one of the walls or himself as follows.

* If there existed no mirror, he saw the wall at (8, 7.5)
* If there existed one mirror between two poles at (8, 7) and (8, 8), he saw the wall at (7.5, 8). (Let us denote the line between these two poles by (8, 7)-(8, 8).)
* If there were four mirrors on (8, 7)-(8, 8), (7, 8)-(8, 8), (0, 0)-(0, 1) and (0, 0)-(1, 0), he saw himself at (0.75, 0.25).
* If there were four mirrors on (2, 1)-(2, 2), (1, 2)-(2, 2), (0, 0)-(0, 1) and (0, 0)-(1, 0), he saw himself at (0.75, 0.25)



Your job is to write a program that reports the location at which the thief saw one of the walls or himself with the given mirror arrangements.



Input

The input contains multiple data sets, each representing how to equip the room with mirrors. A data set is given in the following format.


n
d1 i1 j1
d2 i2 j2
. . .
dn in jn


The first integer n is the number of mirrors, such that 0 ≤ n ≤ 144. The way the k-th (1 ≤ k ≤ n) mirror is fixed is given by dk and (ik,jk). dk is either 'x' or 'y', which gives the direction of the mirror. If dk is 'x', the mirror is fixed on (ik, jk)-(ik + 1, jk). If dk is 'y', the mirror is fixed on (ik,jk) (ik,jk + 1). The end of the input is indicated by a negative integer.

Output

For each data set, your program should output the location (x,y) at which the thief saw one of the walls or himself. The location should be reported in a line containing two integers which are separated by a single space and respectively represent x and y in centimeter as the unit of length. No extra lines nor spaces are allowed.

Example

Input

0
1
y 8 7
4
y 8 7
x 7 8
y 0 0
x 0 0
4
y 2 1
x 1 2
y 0 0
x 0 0
-1


Output

800 750
750 800
75 25
75 25

Solution (in CPP):

Solution:
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cassert>
#include<iomanip>
#include<complex>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
#define pow2(a) ((a)*(a))

using namespace std;

// ------------------------
class Point
{
  public:
  double x,y;

  Point(double x = -1,double y = -1): x(x),y(y){}

  Point operator + (Point p ){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}

  bool operator < (const Point& p) const
  { return x != p.x?x<p.x:y<p.y; }

  bool operator == (const Point& p)const
  { return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS; }

};

struct Segment
{
  Point p1,p2;
  Segment(Point p1 = Point(-1,-1),Point p2 = Point(-1,-1)):p1(p1),p2(p2){}

  bool operator == (const Segment& a)const
  {
    return p1 == a.p1 && p2 == a.p2;
  }
};

ostream& operator << (ostream& os,const Point& a)
{
  os << "(" << a.x << "," << a.y << ")";
}

ostream& operator << (ostream& os,const Segment& a)
{
  os << a.p1 << " " << a.p2;
}

typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;

double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }

double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }

double norm(Point a){ return a.x*a.x+a.y*a.y; }

double abs(Point a){ return sqrt(norm(a)); }

bool pequals(Point a,Point b){ return equals(a.x,b.x) && equals(a.y,b.y); }

Point rotate(Point a,double rad){ return Point(cos(rad)*a.x - sin(rad)*a.y,sin(rad)*a.x + cos(rad)*a.y); }

double toRad(double agl){ return agl*M_PI/180.0; }

int ccw(Point p0,Point p1,Point p2)
{
  Point a = p1-p0;
  Point b = p2-p0;
  if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS)return CLOCKWISE;
  if(dot(a,b) < -EPS)return ONLINE_BACK;
  if(norm(a) < norm(b))return ONLINE_FRONT;
  return ON_SEGMENT;
}

bool intersectLL(Line l, Line m) {
  return abs(cross(l.p2-l.p1, m.p2-m.p1)) > EPS || // non-parallel
         abs(cross(l.p2-l.p1, m.p1-l.p1)) < EPS;   // same line
}
bool intersectLS(Line l, Line s) {
  return cross(l.p2-l.p1, s.p1-l.p1)*       // s[0] is left of l
         cross(l.p2-l.p1, s.p2-l.p1) < EPS; // s[1] is right of l
}
bool intersectLP(Line l,Point p) {
  return abs(cross(l.p2-p, l.p1-p)) < EPS;
}
bool intersectSS(Line s, Line t) {
  return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2) <= 0 &&
         ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2) <= 0;
}
bool intersectSP(Line s, Point p) {
  return abs(s.p1-p)+abs(s.p2-p)-abs(s.p2-s.p1) < EPS; // triangle inequality
}

Point projection(Line l,Point p) {
  double t = dot(p-l.p1, l.p1-l.p2) / norm(l.p1-l.p2);
  return l.p1 + (l.p1-l.p2)*t;
}
Point reflection(Line l,Point p) {
  return p + (projection(l, p) - p) * 2;
}

Point crosspoint(Line l, Line m) {
  double A = cross(l.p2 - l.p1, m.p2 - m.p1);
  double B = cross(l.p2 - l.p1, l.p2 - m.p1);
  if (abs(A) < EPS && abs(B) < EPS) return m.p1; // same line
  if (abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
  return m.p1 +   (m.p2 - m.p1) * (B / A);
}



// -^-^-^-^-^-^-^-^-^-^-^-^

struct Mirror
{
  Segment seg;
  int type;//0 : mirror, 1 : thief, 2 : wall
  Mirror(Segment seg=Segment(),int type=inf):seg(seg),type(type){}
};

int n;
const Point thief(0.75,0.25);

int getTheIndex(Segment beam,vector<Mirror> &vec,int stp)
{
  int res = -inf;
  double mdist = inf;
  rep(i,vec.size())
    {
      if(i == 0)
	{
	  if(!intersectSP(beam,thief))continue;
	}
      else
	{ 
	  if(!intersectSS(beam,vec[i].seg))continue;
	}
      if(stp == i)continue;

      Point cp = crosspoint(beam,vec[i].seg);      

      if(i == 0)cp = thief;
      double dist = sqrt(pow2(beam.p1.x-cp.x)+pow2(beam.p1.y-cp.y));
      if(!equals(mdist,dist) && mdist > dist)
	{
	  mdist = dist;
	  res = i;
	}
    }
  return res;
}

void compute(vector<Mirror> &vec)
{
  Point sp = Point(0.75,0.25);
  Point middle = Point(1,0.5) ;
  Vector vect = middle - sp;
  vect = (vect/abs(vect))*100 + sp;
  Segment beam;
  int index = 0;

  int phase = 1;
  while(true)
    {
      beam = Segment(sp,vect);

      index = getTheIndex(beam,vec,index);

      Point cp = crosspoint(vec[index].seg,beam);
      if(index == 0)cp = thief;

      if(vec[index].type != 0)
	{
	  cout << (int)(float)(cp.x*100) << " " << (int)(float)(cp.y*100) << endl;
	  return;
	}

      sp = cp;
      vect = reflection(vec[index].seg,vect);
    }
}


int main()
{
  while(cin >> n,n != -1)
    {
      vector<Mirror> vec;
      vec.push_back(Mirror(Segment(Point(0.75,0.25),Point(0.75,0.25)),1));

      rep(i,n)
	{
	  char c;
	  double x,y;
	  cin >> c >> x >> y;
	  if(c == 'x') vec.push_back(Mirror(Segment(Point(x,y),Point(x+1,y)),0));
	  else vec.push_back(Mirror(Segment(Point(x,y),Point(x,y+1)),0));
	}

      rep(y1,9)rep(x1,9)REP(y2,y1,9)REP(x2,x1,9)
	if(abs(x1-x2) + abs(y1-y2) != 1)continue;
	else if((x1 == 0 || x1 == 8 || y1 == 0 || y1 == 8) && (x2 == 0 || x2 == 8 || y2 == 0 || y2 == 8))
	  {
	    Segment seg = Segment(Point(x1,y1),Point(x2,y2));
	    bool out = false;
	    REP(k,1,n+1)
	      if(seg == vec[k].seg)
		{
		  out = true;
		  break;
		}

	    seg = Segment(Point(x2,y2),Point(x1,y1));
	    REP(k,1,n+1)
	      if(seg == vec[k].seg)
	      {
		out = true;
		break;
	      }

	    if(!out)
	      vec.push_back(Mirror(seg,2));
	  }
  
      compute(vec);

    }
  return 0;
}