Given two numbers $N$ and $\mbox{M}$. $N$ indicates the number of elements in the array $A[](1-indexed)$ and $\mbox{M}$ indicates number of queries. You need to perform two types of queries on the array $\boldsymbol{A\left[\right]}$.

You are given $\mbox{M}$ queries. Queries can be of two types, type 1 and type 2.

Type 1 queries are represented as 1 i j : Modify the given array by removing elements from $\boldsymbol{i}$ to $j$ and adding them to the front.

Type 2 queries are represented as 2 i j : Modify the given array by removing elements from $\boldsymbol{i}$ to $j$ and adding them to the back.

Your task is to simply print $\left|A[1]-A[N]\right|$ of the resulting array after the execution of $\mbox{M}$ queries followed by the resulting array.

Note While adding at back or front the order of elements is preserved.

Input Format

First line consists of two space-separated integers, $N$ and $\mbox{M}$.

Second line contains $N$ integers, which represent the elements of the array.

$\mbox{M}$ queries follow. Each line contains a query of either type 1 or type 2 in the form $\textbf{type i j}$

Constraints

$1\leq N,M\leq10^5$

$1\leq A[i]\leq10^9$

$1\leq i\leq j\leq N$

Output Format

Print the absolute value i.e. $abs(A[1]-A[N])$ in the first line.

Print elements of the resulting array in the second line. Each element should be seperated by a single space.

Sample Input
8 4
1 2 3 4 5 6 7 8
1 2 4
2 3 5
1 4 7
2 1 4

Sample Output
1
2 3 6 5 7 8 4 1

Explanation

Given array is $\{1,2,3,4,5,6,7,8\}$.

After execution of query $1\:\text{}2\:\text{}4$, the array becomes $\{2,3,4,1,5,6,7,8\}$.

After execution of query$2\:\text{}3\:\text{}5$, the array becomes $\{2,3,6,7,8,4,1,5\}$.

After execution of query $\textbf{1}\:4\:7$, the array becomes $\{7,8,4,1,2,3,6,5\}$.

After execution of query $2\:\text{}1\:\text{}4$, the array becomes $\{2,3,6,5,7,8,4,1\}$.

Now $\left|A[1]-A[N]\right|$ is $|(2-1)|$ i.e. $1$ and the array is $23657841$

见题面

见题面