***E. Correct Bracket Sequence Editor( NO OF BRACKETS REMAIN AFTER PERFORMING SOME PAIR WISE DELETE OPERATION )

E. Correct Bracket Sequence Editor

Recently Polycarp started to develop a text editor that works only with correct bracket sequences (abbreviated as CBS).

Note that a bracket sequence is correct if it is possible to get a correct mathematical expression by adding "+"-s and "1"-s to it. For example, sequences "(())()", "()" and "(()(()))" are correct, while ")(", "(()" and "(()))(" are not. Each bracket in CBS has a pair. For example, in "(()(()))":

• 1st bracket is paired with 8th,
• 2d bracket is paired with 3d,
• 3d bracket is paired with 2d,
• 4th bracket is paired with 7th,
• 5th bracket is paired with 6th,
• 6th bracket is paired with 5th,
• 7th bracket is paired with 4th,
• 8th bracket is paired with 1st.

Polycarp's editor currently supports only three operations during the use of CBS. The cursor in the editor takes the whole position of one of the brackets (not the position between the brackets!). There are three operations being supported:

• «L» — move the cursor one position to the left,
• «R» — move the cursor one position to the right,
• «D» — delete the bracket in which the cursor is located, delete the bracket it's paired to and all brackets between them (that is, delete a substring between the bracket in which the cursor is located and the one it's paired to).

After the operation "D" the cursor moves to the nearest bracket to the right (of course, among the non-deleted). If there is no such bracket (that is, the suffix of the CBS was deleted), then the cursor moves to the nearest bracket to the left (of course, among the non-deleted).

There are pictures illustrated several usages of operation "D" below.

All incorrect operations (shift cursor over the end of CBS, delete the whole CBS, etc.) are not supported by Polycarp's editor.

Polycarp is very proud of his development, can you implement the functionality of his editor?

Input

The first line contains three positive integers n, m and p (2 ≤ n ≤ 500 000, 1 ≤ m ≤ 500 000, 1 ≤ p ≤ n) — the number of brackets in the correct bracket sequence, the number of operations and the initial position of cursor. Positions in the sequence are numbered from left to right, starting from one. It is guaranteed that n is even.

It is followed by the string of n characters "(" and ")" forming the correct bracket sequence.

Then follow a string of m characters "L", "R" and "D" — a sequence of the operations. Operations are carried out one by one from the first to the last. It is guaranteed that the given operations never move the cursor outside the bracket sequence, as well as the fact that after all operations a bracket sequence will be non-empty.

Output

Print the correct bracket sequence, obtained as a result of applying all operations to the initial sequence.

Examples

input

8 4 5
(())()()
RDLD

output

()

input

12 5 3
((()())(()))
RRDLD

output

(()(()))

input

8 8 8
(())()()
LLLLLLDD

output

()()

Note

In the first sample the cursor is initially at position 5. Consider actions of the editor:

1. command "R" — the cursor moves to the position 6 on the right;
2. command "D" — the deletion of brackets from the position 5 to the position 6. After that CBS takes the form (())(), the cursor is at the position 5;
3. command "L" — the cursor moves to the position 4 on the left;
4. command "D" — the deletion of brackets from the position 1 to the position 4. After that CBS takes the form (), the cursor is at the position 1.

Thus, the answer is equal to ().

----------------------------------------------------------EDITORIAL--------------------------------------------------------------------

THIS PROBLEM CAN BE EASILY SOLVED IF SOME HAVE  SOLVED THIS PROBLEM

http://gautamimp.blogspot.in/2015/11/goodvesselsdiv2-d.html

this problem is a  part   of the above problem , 

approach 

Let's solve this problem in the following way. At first with help of stack let's calculate the array pos, where pos[i] equals to the position of the bracket which paired for the bracket in the position i. Then we need to use two arrays left and right. Then left[i] will equals to the position of the closest to the left bracket which did not delete and right[i] will equals to the position of the closest to the right bracket which did not delete. If there are no such brackets we will store -1 in the appropriate position of the array.

Let's the current position of the cursor equals to p. Then if the current operation equals to \texttt{L} let's make p = left[p] and if the current operation equals to \texttt{R} let's make p = right[p]. We need now only to think how process the operation \texttt{D}.

Let lf equals to p and rg equals to pos[p]. If lf > rg let's swap them. Now we know the ends of the substring which we need to delete now. If right[rg] =  =  - 1 we need to move p to the left (p = left[lf]), else we need to move p to the right (p = right[rg]). Now we need to recalculate the links for the ends of the deleted substring. Here we need to check is there any brackets which we did not deleted to the left and to the right from the ends of the deleted substring.

To print the answer we need to find the position of the first bracket which we did not delete and go through all brackets which we did not delete (with help of the array right) and print all such brackets. To find the position of the first bracket which we did not delete we can store in the array all pairs of the ends of substrings which we deleted, then sort this array and find the needed position. Bonus: how we can find this position in the linear time?

-----------------------------------------------------CODE-------------------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

set<int> se;

int nextt[1000000];

int prevv[1000000];

int matching[1000000];

int used[10000000];

int main()

 {

  int n,o,ini;

   cin>>n>>o>>ini;

   for(int i=1;i<=n;i++) 

  {

  

   nextt[i]=i+1;

   prevv[i]=i-1;

  }

   

     string br,op;

    cin>>br>>op;

    stack<int> s;

     for(int i=1;i<=n;i++)

       {

         if(br[i-1]=='(') s.push(i);

         else

            {

            int last=s.top();

            s.pop();

            matching[last]=i;

            matching[i]=last;

         

}

 }

 

 

 for(int i=0;i<o;i++)

  {

     char ty=op[i];

     if(ty=='D')

        {

       

          int l=ini;

          int r=matching[ini];

          if(l>r) swap(l,r);

          

      

          

          for(int i=l;i<=r;)

               {

               

               

                used[i]=1;

                  nextt[prevv[i]]=nextt[i];

                  prevv[nextt[i]]=prevv[i];

                  i=nextt[i];

             

 }

 ini=nextt[r];

 if(ini==n+1)

  {

    ini=prevv[r];

  }

 }

 else if(ty=='R')

  {

  

     ini=nextt[ini];

     if (ini==n+1) ini=prevv[i];

     

  }

  else if(ty=='L')

   {

     ini=prevv[ini];

     if(ini==0) ini=nextt[i];

     

   }

  }

  

  for(int i=1;i<=n;i++)

   if(!used[i])cout<<br[i-1];   

 

 }

***D. Mike and Feet( FIND MAXIMUM OF SLIDING FROM 1 TO N )

D. Mike and Feet

Mike is the president of country What-The-Fatherland. There are n bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to n from left to right. i-th bear is exactly ai feet high.

A group of bears is a non-empty contiguous segment of the line. The size of a group is the number of bears in that group. The strengthof a group is the minimum height of the bear in that group.

Mike is a curious to know for each x such that 1 ≤ x ≤ n the maximum strength among all groups of size x.

Input

The first line of input contains integer n (1 ≤ n ≤ 2 × 105), the number of bears.

The second line contains n integers separated by space, a1, a2, ..., an (1 ≤ ai ≤ 109), heights of bears.

Output

Print n integers in one line. For each x from 1 to n, print the maximum strength among all groups of size x.

Examples

input

10
1 2 3 4 5 4 3 2 1 6

output

6 4 4 3 3 2 2 1 1 1 

-------------------------------------------

---------------------------------------------EDITORIAL-----------------------------------------------------

For each i, find the largest j that aj < ai and show it by li (if there is no such j, then li = 0).

Also, find the smallest j that aj < ai and show it by ri (if there is no such j, then ri = n + 1).

This can be done in O(n) with a stack. Pseudo code of the first part (second part is also like that) :

stack s // initially empty
for i = 1 to n
     while s is not empty and a[s.top()] >= a[i]
          do s.pop()
     if s is empty
          then l[i] = 0
     otherwise
          l[i] = s.top()
     s.push(i)

Consider that you are asked to print n integers, ans1, ans2, ..., ansn. Obviously, ans1 ≥ ans2 ≥ ... ≥ ansn.

For each i, we know that ai can be minimum element in groups of size 1, 2, ..., ri - li - 1.

Se we need a data structure for us to do this:

We have array ans1, ans2, ..., ansn and all its elements are initially equal to 0. Also, n queries. Each query gives x, val and want us to perform ans1 = max(ans1, val), ans2 = max(ans2, val), ..., ansx = max(ansx, val). We want the final array.

This can be done in O(n) with a maximum partial sum (keeping maximum instead of sum), read here for more information about partial sum.

Time complexity: 

=============================CODE==============================================

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

stack<pair<lli,int> > s;

lli arr[1000000];

int fforward[1000000];

int bbackward[1000000];

vector<lli> ans;

vector<pair<int,lli> > span;

int main()

 {

  int n;

  cin>>n;

  for(int i=0;i<n;i++)

    {

     cin>>arr[i];

  }

  

 

  for(int i=0;i<n;i++)

   {

    //cout<<" going to use "<<arr[i]<<endl;

  if( s.empty() || s.top().first<=arr[i] )

     {

 //     cout<<" push"<<endl;;

  s.push({arr[i],i});

    }

  else

   {

    while(!s.empty() && s.top().first>arr[i])

     {

       

      fforward[s.top().second]=(i-s.top().second);

      // cout<<"pop "<<s.top().first<<" "<<" ans is "<<fforward[s.top().second]<<endl;

      s.pop();

     

 }

 s.push({arr[i],i});

}

 

}

while(!s.empty())

{

fforward[s.top().second]=(n-s.top().second);

s.pop();

}

/*for(int i=0;i<n;i++) cout<<fforward[i]<<" ";

 cout<<endl;*/

 

 

  for(int i=n-1;i>=0;i--)

       {

    //cout<<" going to use "<<arr[i]<<endl;

  if( s.empty() || s.top().first<=arr[i] )

     {

 //     cout<<" push"<<endl;;

  s.push({arr[i],i});

    }

  else

   {

    while(!s.empty() && s.top().first>arr[i])

     {

       

      bbackward[s.top().second]=(s.top().second-i);

      // cout<<"pop "<<s.top().first<<" "<<" ans is "<<fforward[s.top().second]<<endl;

      s.pop();

     

 }

 s.push({arr[i],i});

}

 

}

while(!s.empty())

{

bbackward[s.top().second]=(s.top().second+1);

s.pop();

}

  

  for(int i=0;i<n;i++)

   {

    span.push_back({fforward[i]+bbackward[i]-1,arr[i]});

    // cumulated[i]=fforward[i]+bbackward[i]-1;

}

 // for(int i=0;i<n;i++)cout<<cumulated[i]<<" ";

  //cout<<endl;

  sort(span.begin(),span.end());

  int start=n-1;

  set<lli> sset;

  for(int sp=n;sp>=1;sp--)

   {

    while(start>=0 && span[start].first>=sp)

     {

      sset.insert(span[start].second);

      start--;

 }

ans.push_back(*sset.rbegin());

}

for(int i=n-1;i>=0;i--) cout<<ans[i]<<" ";

 

 }