SP8429 BTCODE_K - Array Sorting

Sumit specialises in sorting algorithms, and Abhishek decides to test Sumit's coding skills. An array of 'n' numbers a\[0\], a\[1\], a\[2\], ..., a\[n-1\] is given. Abhishek gives a sequence of inputs of the form "v i j". Each input is either a query or an update (query if 'v' is 0, update otherwise). For any input of the form "0 i j" ,Sumit's output should be as follows: If the subarray a\[i\], a\[i+1\], ... a\[j\] is unsorted, output 0. If the subarray a\[i\], a\[i+1\], ... a\[j\] is sorted in non-descending order, output 1. If the subarray a\[i\], a\[i+1\], ... a\[j\] is sorted in non-ascending order, output 2. If the subarray a\[i\], a\[i+1\], ... a\[j\] is sorted in both non-ascending and non-descending order (i.e, if all the elements in the range are equal), output 3. Any other input "v i j" (v!=0) should be treated as an update, as follows: For each element in the subarray a\[i\], a\[i+1\], ... a\[j\], Sumit has to replace the element a\[k\] with v-a\[k\]. Sumit is really tired and does not want to write a program. Can you write a program for Sumit, which responds to Abhishek's instructions?

The first line of input contains 2 space separated integers 'n' and 'q'. The second line contains 'n' integers a\[0\], a\[1\], ....., a\[n-1\]. Each of the next 'q' lines contain 3 integers 'v', 'i', 'j'.

For each query, output a single integer 0, 1, 2 or 3, denoting the answer.