Mr. X

0

0 votes
Very-Easy
Problem

A Video game has Q levels and Mr. X is a superhero in that game. Now Mr. X is on a strange planet full of monsters and has to complete all the level to go back home safely.

In the game, there are N buildings in a line. Each building has a number A[i]. There is a tunnel (full of monsters) from each building which connects building at ith index to the buildings at (i+A[i])th index and (i-A[i])th index. If (i+A[i])>N or (i-A[i])<=0 then Mr X will be in Safe zone and will advance to the next level.

Now, at each level of the game either of the two situation can occur : -

a) Mr X will find himself in building 'x' . Now he has to decide in which direction he should proceed(Left or Right). Once he starts to move on the building left of x then he can never move in right direction at that level of the game and vice versa. Since the tunnels are full of monsters so Mr. X wants to reach the safe spot while using tunnels minimum number of times.
So, he need your help to figure out in which direction he should proceed and minimum number of time he will have to use tunnels.

b) The monster can change the number of building x to y. i.e A[x]=y.This is supposed to be the bonus level for Mr X.
Whenever this situation occurs, Mr X will be promoted to next level automatically.

INPUT :

First line contains N and Q. Number of buildings in the game and number of levels in the game respectively.
Second line contains N space seprated integers A[i] (initial number on each building).
Next Q line contains
1 x (Situation=1, represents that Mr X is at building x and has to chose the direction in which he has to proceed and count of minimum number of times he will use tunnel).
0 a b (Situation=0, represents that monster is going to change the number of building a to b. i.e A[a]=b)

Output:

For every level of situation=1 , Print the direction in which Mr X should proceed ("LEFT" if he chose left direction or "RIGHT" if he chose right direction)
followed by a space seprated integer (count of minimum number of times Mr X will use Tunnel) followed by new line.
If count of use of tunnel in right direction is equal to count of use of tunnel in left direction , then print "RIGHT".
NOTE:
Indexing of building starts from 1.
Constraints:

1<=N<=10^5
1<=Q<=10^5
1<=x<=N
1<=A[i]<=10^5

Sample Input:

8 6
1 1 1 1 1 2 8 2
1 1
0 3 3
1 1
0 3 4
1 2
1 6

Output:

LEFT 1
LEFT 1
LEFT 2
RIGHT 2

Author - Vivek Ojha

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?