*****E. Holes( (SQRT + DP ) NUMBER OF STEP IN WHICH REACH AT SOME INDEX > N )

E. Holes

Little Petya likes to play a lot. Most of all he likes to play a game «Holes». This is a game for one person with following rules:

There are N holes located in a single row and numbered from left to right with numbers from 1 to N. Each hole has it's own power (hole number i has the power ai). If you throw a ball into hole i it will immediately jump to hole i + ai, then it will jump out of it and so on. If there is no hole with such number, the ball will just jump out of the row. On each of the M moves the player can perform one of two actions:

• Set the power of the hole a to value b.
• Throw a ball into the hole a and count the number of jumps of a ball before it jump out of the row and also write down the number of the hole from which it jumped out just before leaving the row.

Petya is not good at math, so, as you have already guessed, you are to perform all computations.

Input

The first line contains two integers N and M (1 ≤ N ≤ 105, 1 ≤ M ≤ 105) — the number of holes in a row and the number of moves. The second line contains N positive integers not exceeding N — initial values of holes power. The following M lines describe moves made by Petya. Each of these line can be one of the two types:

• 0 a b
• 1 a

Type 0 means that it is required to set the power of hole a to b, and type 1 means that it is required to throw a ball into the a-th hole. Numbers a and b are positive integers do not exceeding N.

Output

For each move of the type 1 output two space-separated numbers on a separate line — the number of the last hole the ball visited before leaving the row and the number of jumps it made.

Examples

input

8 5
1 1 1 1 1 2 8 2
1 1
0 1 3
1 1
0 3 4
1 2

output

8 7
8 5
7 3

============================EDITORIAL ===================================

THIS PROBLEM CAN BE SOLVED WITH SQRT DECOMPOSITION ,  AND  SOME BASIC CONCEPT OF DYNAMIC PROGRAMMING , 

FIRST OF ALL WE DIVIDE THE ENTIRE HOLES IN TO BLOCKS , EACH BLOCK WILL CONTAIN AT MAX 350 HOLES ,

NOW  WE WILL KEEP TRACK OF 3 THINGS 

1-> NEXT[i] = IF WE ARE CURRENTLY AT SOME INDEX i , SO ITS CURRENT BLOCK WILL BE i/350( SAY IT x) , NEXT[i]  WILL CONTAIN THE  FIRST INDEX IN NEXT BLOCK(x+1)  WHICH   IT  WILL REACH ... IN ITS MOVE ..

2-> COUNT[i]= IF WE ARE AT INDEX i NUMBER OF MOVES REQUIRED TO LEAVE  THE CURRENT BLOCK AND REACH TO THE NEXT BLOCK .. ( ie FORM  BLOCK x TO x+1  )

MEANS NUMBER OF MOVE IN THE SAME BLOCK BEFORE REACHING TO NEXT BLOCK

3->LAST[i] = IF WE ARE AT INDEX i ,   IT WILL CONTAIN THE LAST INDEX( IN THE CURRENT BLOCK )  WHICH COVER WHILE LEAVING CURRENT BLOCK 

NOTE:- ALWAYS NEXT[i]= LAST[i]+ARR[LAST[i]] SINCE FORM LAST INDEX WE MAKE A JUMP TO REACH TO THE NEXT INDEX IN NEXT BLOCK...

ALL THESE 3 ARRAY CAN BE CALCULATED USING BACKWARD DP .......

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

int fix(int i)

 {

//if ith index will directly go out of the block in next move  than  steps taken in the block=1,   //next=i+arr[i]  and last index  used in the same block will be i ..

    if((i+arr[i])>=n || (i+arr[i])/bs!=i/bs) 

         {

            nexxt[i]=i+arr[i];

cnt[i]=1;

last[i]=i;

}

// else if  remain i the same block , than count will be equal to count  of i+arr[i] , and also 

//  next   will be the next of i +arr[i] , ans last will be also same as last of i+arr[i] 

        else

{

cnt[i]=1+cnt[i+arr[i]];

nexxt[i]=nexxt[i+arr[i]];

// cout<<" set last of "<<i<<" as "<<last[i+arr[i]]<<endl;

last[i]=last[i+arr[i]];

}

 }

now 

we have 2 types of  query ,

for type 1 query , we just need to count  the number for  jump , which can be easily calculate now 

start from the current node and add count[cur] for the current node( which will give answer for the no of moves taken inside the block ) ans than jump to the next block  ,, till no reach to  some index>=n

                            if(type)

    {

    int ans=0;

    int cur; 

    scanf("%d",&cur);

cur--;

    int l=last[cur];

    while(cur<n)

           {

             ans+=cnt[cur];//  add moves within same block 

             l=last[cur];//  this node will be the last index used in current block 

             cur=nexxt[cur]; //  go to next block 

}

printf("%d %d\n",(l+1),ans);

  }

for type 0 query , 

suppose we  update the value at index a , what are index affected due to that ,,

obviously some  indexs < a since these   are the index can go through  'a'

now according to  our method we have calculated next[i] , count[i] , and last[i] for each block 

so the answer of the  index which lies in some block < than the block of 'a'  can be affected but we need to update the next , count, and last of  index in the current block only , since  index in other block < than current block   can use the    values of of this block ..( if they reach in this block).

                           else// calling fix function for all index < a and in the  block of a 

  {

  int  a,b;

  scanf("%d %d",&a,&b);

   a--;

   arr[a]=b;

  int cur=a;

  while(cur>=0 && cur/bs==a/bs)

   {

    fix(cur);

    cur--;

 }

  }

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

#include<bits/stdc++.h>

using namespace std;

int arr[1000000];

int nexxt[1000000];

int cnt[1000000];

int last[1000000];

int bs=350;

 int n,q;

int fix(int i)

 {

    if((i+arr[i])>=n || (i+arr[i])/bs!=i/bs) 

    {

    nexxt[i]=i+arr[i];

cnt[i]=1;

last[i]=i;

}

else

{

cnt[i]=1+cnt[i+arr[i]];

nexxt[i]=nexxt[i+arr[i]];

// cout<<" set last of "<<i<<" as "<<last[i+arr[i]]<<endl;

last[i]=last[i+arr[i]];

}

 }

int main()

 {

   

    cin>>n>>q;

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

      { 

      scanf("%d",&arr[i]);

}

 

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

 {

   fix(i);

 }

 

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

  {

  int type;

   scanf("%d",&type);

   if(type)

    {

    int ans=0;

    int cur; 

    scanf("%d",&cur);

cur--;

    int l=last[cur];

    while(cur<n)

           {

             ans+=cnt[cur];

             l=last[cur];

             cur=nexxt[cur]; 

}

printf("%d %d\n",(l+1),ans);

  }

  else

  {

  int  a,b;

  scanf("%d %d",&a,&b);

   a--;

   arr[a]=b;

  int cur=a;

  while(cur>=0 && cur/bs==a/bs)

   {

    fix(cur);

    cur--;

 }

  }

  }

 }

====================================OR===========================

Let's divide all row into blocks of length K=sqrt(N) of consecutive holes. If N is not a complete square, then we will take K=sqrt(N) rounded down. For each hole we will maintain not only it's power (let's call it power[i]), but also the number of the first hole which belongs to other block and which can be reached from the current one with sequence of jumps (let's call it next[i]). Also, for each hole we will maintain the number of jumps required to reach the hole next[i] from the current one (let's call it count[i]). We will consider that there is a fictious hole, which lies after the hole N and it belongs to it's own block.

To answer the query of the first type (when the ball is thrown) we will jump from the hole i to hole next[i] and so on, until we reach the fictious hole. Each time we will add count[i] to the answer. We will jump not more than N/K times.

To maintain the query of the seqond type (when the power of hole i is changed) we will change power[i], next[i] and count[i]. Then for each hole which belongs to the same block as i and has smaller number than i we will update next[i] and power[i] in decreasing order of number of the hole. We will perform not more than K updates.

The complexity is O(Nsqrt(N)).

RACETIME - Race Against Time( in l to r fingd number of numbers <=X ) sqrt decompossition

RACETIME - Race Against Time

As another one of their crazy antics, the N (1 ≤ N ≤ 100,000) cows want Farmer John to race against the clock to answer some of their pressing questions.

The cows are lined up in a row from 1 to N, and each one is holding a sign representing a number, Ai (1 ≤ Ai ≤ 1,000,000,000). The cows need FJ to perform Q (1 ≤ Q ≤ 50,000) operations, which can be either of the following:

• Modify cow i's number to X (1 ≤ X ≤ 1,000,000,000). This will be represented in the input as a line containing the letter M followed by the space-separated numbers i and X.
• Count how many cows in the range [P, Q] (1 ≤ P ≤ Q ≤ N) have Ai ≤ X (0 ≤ X ≤ 1,000,000,000). This will be represented in the input as a line containing the letter C followed by the space-separated numbers P, Q, and X.

Of course, FJ would like your help.

Input

The first line gives the integers N and Q, and the next N lines give the initial values of Ai. Finally, the next Q lines each contain a query of the form "M i X" or "C P Q X".

Output

Print the answer to each 'C' query, one per line.

Example

Input:
4 6
3
4
1
7
C 2 4 4
M 4 1
C 2 4 4
C 1 4 5
M 2 10
C 1 3 9

Output:
2
3
4
2

FJ has 4 cows, whose initial numbers are 3, 4, 1, and 7. The cows then give him 6 operations; the first asks him to count the how many of the last three cows have a number at most 4, the second asks him to change the fourth cow's number to 1, etc.

===================================editorial=====================================

divide the array in sqrt part and each part contain a sorted vector , now iterate  block wise , if a block completely inside   the range than count using b'search ( since content of block is sorted)  else if a block is partially in the range than iterate , in that  block,,

 for update ,  replace and sort the vector of the block ....

================================code===============================================#include<bits/stdc++.h>

using namespace std;

 vector<int> block[1000];

 int arr[1000000];

int main()

 {

  int n,q;

   scanf("%d %d",&n,&q);

       int sq=317;

        int b_size=317;

     if(sqrt(n)*sqrt(n)!=n)

   {

  sq++;

  b_size++;

} 

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

         {

             int a;

            scanf("%d",&a);

            arr[i]=a;

            block[i/b_size].push_back(a);

}

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

{

sort(block[i].begin(),block[i].end());

}

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

{

char type;

 cin>>type;

   if(type=='C')

     {

         int l,r,val;

 scanf("%d %d %d",&l,&r,&val);

 

 int ans=0;

 l--;

 r--;

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

  {

   int bs=i*b_size;

   int be=bs+b_size-1;

   if(l<=bs && r>=be)

       {  

        int count=upper_bound(block[i].begin(),block[i].end(),val)-block[i].begin();

        ans+=count;

 }

 else 

   {

    for( int j = max(bs,l) ; j <= min(be,r);j++ ) // if range have some portion in this block

                                            ans += (arr[j]<=val) ;

}

  }

 

  printf("%d\n",ans);

 }

 else

 {

   int idx;int val;

   scanf("%d %d",&idx,&val);

   idx--;

    int bnum=idx/b_size;

    int remove=arr[idx];

   // int f=0;

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

       {

      if(block[bnum][i]==remove)

         { 

           block[bnum][i]=val;

           arr[idx]=val;

           break;

}

 }

  sort(block[bnum].begin(),block[bnum].end());

 }

}

 }