Given sequence  (a1,a2,⋅⋅⋅,an)=(1,2,⋅⋅⋅,n), Namely  ai=i.

Xiaolan will test this sequence  m  Secondary operation , Every time it may be  a1,a2,⋅⋅⋅,aqi Descending order , Or will  aqi,aqi+1,⋅⋅⋅,an Ascending arrangement .

Request the sequence after the operation is completed .

Input format

The first line of input contains two integers  n,m, Represents the length of the sequence and the number of operations, respectively .

next  m  Line describes the operation on the sequence , Among them  i  The row contains two integers  pi,qi Indicates the operation type and parameters . When  pi=0 Time , Indicates that it will  a1,a2,⋅⋅⋅,aqi
Descending order ; When  pi=1 Time , Indicates that it will  aqi,aqi+1,⋅⋅⋅,an Ascending arrangement .

Output format

Output one line , contain  n  Integer , Adjacent integers are separated by a space , Represents the sequence after the operation is completed .

Data range

about  30% Evaluation cases for ,n,m≤1000;
about  60% Evaluation cases for ,n,m≤5000;
For all profiling cases ,1≤n,m≤10^5,0≤pi≤1,1≤qi≤n.

sample input ：
3 3 0 3 1 2 0 2
sample output ：
3 1 2
Example explanation

The original sequence is  (1,2,3).

The first  1  After step  (3,2,1).

The first  2  After step  (3,1,2).

The first  3  After step  (3,1,2). And the first  2  Same after step operation , Because the first two numbers are in descending order .

analysis ： Let's first briefly analyze several special cases , Take descending order as an example , Suppose we have two consecutive orders , One is to 1~a Descending order , The other is to 1~b Descending order , At this time a and b There are three size relationships , if a and b equal , Then the two commands are equivalent , Just execute one , if a>b, Because at the beginning 1~a In descending order , So obviously 1~b Itself is in descending order , So there is no need to execute the latter command , What if a<b And ? At this time, we must carry out the latter order , But what is the point of executing the previous command ? Because he has been included in the following orders , It is not difficult for us to analyze this example ,
When multiple consecutive descending commands need to be executed , We only need to execute the one with the rightmost boundary （ Because the left boundary is 1）, The rest of the commands are superfluous , Similarly , Simple analysis can be obtained
When multiple consecutive ascending commands need to be executed , We just need to execute the one on the far left of the boundary
（ Because the right boundary is n), Other commands are also redundant . After processing the answers in this way, the commands we need to execute are arranged in ascending and descending order , It's an ascending order, then a descending order, and then an ascending order ……, of course , It's not enough just to deal with it like this , We also need to do other processing on the command ：

Before we assume i The right boundary of two descending commands is decreasing , The left boundary of the ascending command is incremented （ In order to conclude and prove that the effective order conforms to this law ）
, The first i The first command is right 1~a Descending order , The first i+1 The first command is right b~n Ascending order , The first i+2 The first command is right 1~a+x Descending order

Because before i individual
The right boundary of the descending command is decreasing , The left boundary of the ascending command is incremented , Therefore, we can only update the junction of two adjacent command intervals every time , And it's getting smaller and smaller , Suddenly, a number larger than the previous one appears on the right boundary of the descending command （ The left boundary of the ascending command has a number smaller than the previous one, which is also the same analysis method ）, Let's see how we can simplify the command , Previous analysis can let us know , Our first i First command and second command i+1 The number of commands that can be updated is only the interval [b,a] Number on （ because
front i individual
The right boundary of the descending command is decreasing , The left boundary of the ascending command is incremented , that is b Interval sum on the left a The interval on the right is already orderly ）, But the number of this interval is called interval [1,a+x] Covered , Then the updates of the previous two commands will be disrupted again by this command , So the first two commands can be directly discarded , Until a descending command is found, the boundary is greater than a+x until , So we
In the final valid command, the right boundary of the descending command is decreasing , The left boundary of the ascending command is incremented .

When the problem is analyzed, the order will be handled , The way to handle the answer is in the code ：
#include<cstdio> #include<iostream> #include<cstring> #include<vector>
#include<algorithm> #include<map> #include<cmath> #include<queue> using
namespace std; const int N=100010; typedef pair<int,int> PII; PII stk[N]; int
ans[N],top; int main() { int n,m; cin>>n>>m; while(m--) { int p,q;
scanf("%d%d",&p,&q); if(!p) { while(top&&stk[top].first==0)
q=max(q,stk[top--].second);// Find the maximum right boundary in continuous descending commands
while(top>=2&&stk[top-1].second<=q) top-=2;// If the current right boundary is greater than the right boundary of the previous command , The previous command is invalid
stk[++top]={0,q};// Stack the current command } else if(top) { while(top&&stk[top].first==1)
q=min(q,stk[top--].second);// Find the maximum left boundary in continuous ascending commands
while(top>=2&&stk[top-1].second>=q) top-=2;// If the current left boundary is less than the left boundary of the previous command , The previous command is invalid
stk[++top]={1,q};// Stack the current command } } int k=n,l=1,r=n; for(int i=1;i<=top;i++) {
if(stk[i].first==0) while(r>stk[i].second&&l<=r) ans[r--]=k--; else
while(l<stk[i].second&&l<=r) ans[l++]=k--; if(l>r) break; } if(top%2)// Ascending commands should be processed
while(l<=r) ans[l++]=k--; else// Descending commands should be processed while(l<=r) ans[r--]=k--; for(int
i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }

Technology
Daily Recommendation