{"id":"2734446b-eb2a-4c17-9ed1-9c0d2b272623","name":"Trampoline","description":"PepCoder likes to play with trampolines and add some new flavours to it. This time he has N trampolines in a row from left to right numbered from 1 to N. Each Trampoline has its own jump power(trampoline numbered i has a jump power of pi ). If PepCoder jumps to trampoline i he immediately jumps to trampoline i + pi , then he will jump out of it and so on.If there is no trampoline with such number he falls on the ground and marks the last trampoline he jumped from as bad. U are given Q queries where each query can be of 2 types\r\n0: Set the power of trampoline a to b,\r\n1: Jump to trampoline a and count the number of jumps he makes before falling on the ground and also note down the number of bad trampoline.\r\n","inputFormat":"1: First line contains 2 space separated numbers N and Q,\r\n2: Second line contains N space separated integers p1 p2 p3 ..... pN\r\n3: Next Q lines contains queries of format:-\r\n0 a b\r\n1 a\r\n","outputFormat":"For each query of type 1 print 2 space separated numbers on a separate line, the number of the bad hole and numbers of jumps PepCoder made before falling to the ground.","constraints":"1 <= Q <= 10 ^5\r\n1 <= N <= 10^5\r\n1 <= a <= N\r\n1 <= b <= 10 ^ 6\r\na and b are always valid","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws IOException {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n \r\n // use BufferedReader created above for taking input\r\n \r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"8 5\r\n1 1 1 1 1 2 8 2\r\n1 1\r\n0 1 3\r\n1 1\r\n0 3 4\r\n1 2\r\n","sampleOutput":"8 7\r\n8 5\r\n7 3\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"ed294401-c1be-4c10-a3f7-3e2e4f8d9755","name":"Range Queries For Experts","slug":"range-queries-for-experts-903","type":0},{"id":"239cc04b-e6e3-4d31-b45e-7eb280c3807b","name":"Trampoline","slug":"trampoline","type":1}],"next":{"id":"6994e031-60ea-4219-843b-2b48a9a7e132","name":"Sparse Table","type":1,"slug":"sparse-table"},"prev":{"id":"179d9606-6fc5-4e3a-935e-46a5c0060175","name":"Create Sorted Array Through Instructions","type":1,"slug":"create-sorted-array-through-instructions"}}}

Trampoline

PepCoder likes to play with trampolines and add some new flavours to it. This time he has N trampolines in a row from left to right numbered from 1 to N. Each Trampoline has its own jump power(trampoline numbered i has a jump power of pi ). If PepCoder jumps to trampoline i he immediately jumps to trampoline i + pi , then he will jump out of it and so on.If there is no trampoline with such number he falls on the ground and marks the last trampoline he jumped from as bad. U are given Q queries where each query can be of 2 types 0: Set the power of trampoline a to b, 1: Jump to trampoline a and count the number of jumps he makes before falling on the ground and also note down the number of bad trampoline.

{"id":"2734446b-eb2a-4c17-9ed1-9c0d2b272623","name":"Trampoline","description":"PepCoder likes to play with trampolines and add some new flavours to it. This time he has N trampolines in a row from left to right numbered from 1 to N. Each Trampoline has its own jump power(trampoline numbered i has a jump power of pi ). If PepCoder jumps to trampoline i he immediately jumps to trampoline i + pi , then he will jump out of it and so on.If there is no trampoline with such number he falls on the ground and marks the last trampoline he jumped from as bad. U are given Q queries where each query can be of 2 types\r\n0: Set the power of trampoline a to b,\r\n1: Jump to trampoline a and count the number of jumps he makes before falling on the ground and also note down the number of bad trampoline.\r\n","inputFormat":"1: First line contains 2 space separated numbers N and Q,\r\n2: Second line contains N space separated integers p1 p2 p3 ..... pN\r\n3: Next Q lines contains queries of format:-\r\n0 a b\r\n1 a\r\n","outputFormat":"For each query of type 1 print 2 space separated numbers on a separate line, the number of the bad hole and numbers of jumps PepCoder made before falling to the ground.","constraints":"1 <= Q <= 10 ^5\r\n1 <= N <= 10^5\r\n1 <= a <= N\r\n1 <= b <= 10 ^ 6\r\na and b are always valid","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws IOException {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n \r\n // use BufferedReader created above for taking input\r\n \r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"8 5\r\n1 1 1 1 1 2 8 2\r\n1 1\r\n0 1 3\r\n1 1\r\n0 3 4\r\n1 2\r\n","sampleOutput":"8 7\r\n8 5\r\n7 3\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"ed294401-c1be-4c10-a3f7-3e2e4f8d9755","name":"Range Queries For Experts","slug":"range-queries-for-experts-903","type":0},{"id":"239cc04b-e6e3-4d31-b45e-7eb280c3807b","name":"Trampoline","slug":"trampoline","type":1}],"next":{"id":"6994e031-60ea-4219-843b-2b48a9a7e132","name":"Sparse Table","type":1,"slug":"sparse-table"},"prev":{"id":"179d9606-6fc5-4e3a-935e-46a5c0060175","name":"Create Sorted Array Through Instructions","type":1,"slug":"create-sorted-array-through-instructions"}}}
plane

Editor


Loading...

Trampoline

hard

PepCoder likes to play with trampolines and add some new flavours to it. This time he has N trampolines in a row from left to right numbered from 1 to N. Each Trampoline has its own jump power(trampoline numbered i has a jump power of pi ). If PepCoder jumps to trampoline i he immediately jumps to trampoline i + pi , then he will jump out of it and so on.If there is no trampoline with such number he falls on the ground and marks the last trampoline he jumped from as bad. U are given Q queries where each query can be of 2 types 0: Set the power of trampoline a to b, 1: Jump to trampoline a and count the number of jumps he makes before falling on the ground and also note down the number of bad trampoline.

Constraints

1 <= Q <= 10 ^5 1 <= N <= 10^5 1 <= a <= N 1 <= b <= 10 ^ 6 a and b are always valid

Format

Input

1: First line contains 2 space separated numbers N and Q, 2: Second line contains N space separated integers p1 p2 p3 ..... pN 3: Next Q lines contains queries of format:- 0 a b 1 a

Output

For each query of type 1 print 2 space separated numbers on a separate line, the number of the bad hole and numbers of jumps PepCoder made before falling to the ground.

Example

Sample Input

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

Sample Output

8 7 8 5 7 3

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode