Description

有一个外星人控制了你的大脑。一开始你处于原点（0,0）。外星人有一个由(R,U,D,L)组成的长度为M 的操作序列，分别代表(右，上，下，左)。

平面上有N 个关键点，每当外星人给出一个操作，你需要在这个方向上找到最近的一个关键点，并走到那个点上。保证输入数据合法。

上图为第三个样例的图示。

 

Input

第一行两个整数N,M。

接下来N 行，每行两个整数xi,yi，代表第i 个点的坐标。

接下来一行，一个长度为M 的字符串，代表操作序列。

Output

一行两个整数，代表最终你所处的位置。

 

Sample Input

输入1：4 41 11 00 1 0 0RULD输入2：7 50 00 10 -11 01 -13 03 -1DRRUD输入3：10 60 01 12 10 2-1 2-1 32 32 44 32 -1ULURDL

Sample Output

输出1：0 0输出2：3 -1输出3：1 1

 

Data Constraint

56%的数据，N≤3000，M≤3000。

100%的数据，N,M≤100000,xi,yi≤200000。

 两次快排记录一下每个点上下左右能到哪个点就好了...

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 struct data{ 9 int x,y,z;10 }po[100005];11 int n,m,f[100002][5],a;12 string qwq;13 bool comp1(const struct data a,const struct data b){14 if (a.x
            
             >qwq;34 sort(po+1,po+1+n,comp1);35 for (int i=1;i<=n;i++){36 if ((po[i].x==po[i-1].x)&&(po[i].y
             
              po[i-1].y)) {f[po[i].z][1]=po[i-1].z; f[po[i-1].z][0]=po[i].z;}38 }39 sort(po+1,po+1+n,comp2);40 for (int i=1;i<=n;i++){41 if ((po[i].y==po[i-1].y)&&(po[i].x
              
               po[i-1].x)) {f[po[i].z][3]=po[i-1].z; f[po[i-1].z][2]=po[i].z;}43 44 }45 for (int i=0;i