`{"id":"d8cf805d-71dc-46da-baf5-cd4ede61a94d","name":"Prime Divide","description":"You are given an array A of N numbers.\r\nYou need to perform Q operations. Each operation has one of the two type:\r\n\r\n1. 1 l r p: select all numbers between indices l to r which are divisible by p and divide then all by p, here is in set {2, 3 5}.\r\n2. 2 l d: update element at index l to d.\r\n\r\nPrint the final array after performing all operations.","inputFormat":"First line contains single number N denoting size of array\r\nSecond line contains N space seperated numbers A[1] A[2] A[3] ... A[N] denoting elements of array\r\nThird line contains single number Q denoting number of operations\r\nQ following lines contains operations of format\r\n1 l r p or 2 l d","outputFormat":"Print in different lines elements of array after performing all operations.","constraints":"1. 1 &lt;= N &lt;= 10^5\r\n2. 1 &lt;= Q &lt;= 10^5\r\n3. 1 &lt;= l &lt;= r &lt;= N\r\n4. 1 &lt;= A[i], d &lt;= 10^9\r\n5. p belongs to set {2, 3, 5}","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n = Integer.parseInt(read.readLine());\r\n\r\n \r\n\r\n\r\n\r\n }\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5\r\n8 9 12 3 5 \r\n5\r\n1 1 5 3\r\n2 5 9\r\n1 1 5 3\r\n1 2 5 2\r\n2 3 5\r\n","sampleOutput":"8\r\n1\r\n5\r\n1\r\n3\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":"9b3d7d76-b2ca-458f-80a8-4b37d548024a","name":"Segment Tree For Experts","slug":"segment-tree-for-experts-953","type":0},{"id":"5eceac13-61e9-4d38-960d-7b16abd79154","name":"Prime Divide","slug":"prime-divide","type":1}],"next":{"id":"d9f9a7f2-4b92-434b-8a57-8746d6170251","name":"Multiples Of 3","type":1,"slug":"multiples-of-3"},"prev":{"id":"9167f274-6395-4fa1-b521-a700d2d14ff1","name":"Toggle Bulbs","type":1,"slug":"toggle-bulbs"}}}`

Prime Divide

You are given an array A of N numbers. You need to perform Q operations. Each operation has one of the two type: 1. 1 l r p: select all numbers between indices l to r which are divisible by p and divide then all by p, here is in set {2, 3 5}. 2. 2 l d: update element at index l to d. Print the final array after performing all operations.

`{"id":"d8cf805d-71dc-46da-baf5-cd4ede61a94d","name":"Prime Divide","description":"You are given an array A of N numbers.\r\nYou need to perform Q operations. Each operation has one of the two type:\r\n\r\n1. 1 l r p: select all numbers between indices l to r which are divisible by p and divide then all by p, here is in set {2, 3 5}.\r\n2. 2 l d: update element at index l to d.\r\n\r\nPrint the final array after performing all operations.","inputFormat":"First line contains single number N denoting size of array\r\nSecond line contains N space seperated numbers A[1] A[2] A[3] ... A[N] denoting elements of array\r\nThird line contains single number Q denoting number of operations\r\nQ following lines contains operations of format\r\n1 l r p or 2 l d","outputFormat":"Print in different lines elements of array after performing all operations.","constraints":"1. 1 &lt;= N &lt;= 10^5\r\n2. 1 &lt;= Q &lt;= 10^5\r\n3. 1 &lt;= l &lt;= r &lt;= N\r\n4. 1 &lt;= A[i], d &lt;= 10^9\r\n5. p belongs to set {2, 3, 5}","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n = Integer.parseInt(read.readLine());\r\n\r\n \r\n\r\n\r\n\r\n }\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5\r\n8 9 12 3 5 \r\n5\r\n1 1 5 3\r\n2 5 9\r\n1 1 5 3\r\n1 2 5 2\r\n2 3 5\r\n","sampleOutput":"8\r\n1\r\n5\r\n1\r\n3\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":"9b3d7d76-b2ca-458f-80a8-4b37d548024a","name":"Segment Tree For Experts","slug":"segment-tree-for-experts-953","type":0},{"id":"5eceac13-61e9-4d38-960d-7b16abd79154","name":"Prime Divide","slug":"prime-divide","type":1}],"next":{"id":"d9f9a7f2-4b92-434b-8a57-8746d6170251","name":"Multiples Of 3","type":1,"slug":"multiples-of-3"},"prev":{"id":"9167f274-6395-4fa1-b521-a700d2d14ff1","name":"Toggle Bulbs","type":1,"slug":"toggle-bulbs"}}}`

Editor

Prime Divide

medium

You are given an array A of N numbers. You need to perform Q operations. Each operation has one of the two type: 1. 1 l r p: select all numbers between indices l to r which are divisible by p and divide then all by p, here is in set {2, 3 5}. 2. 2 l d: update element at index l to d. Print the final array after performing all operations.

Constraints

1. 1 <= N <= 10^5 2. 1 <= Q <= 10^5 3. 1 <= l <= r <= N 4. 1 <= A[i], d <= 10^9 5. p belongs to set {2, 3, 5}

Format

Input

First line contains single number N denoting size of array Second line contains N space seperated numbers A[1] A[2] A[3] ... A[N] denoting elements of array Third line contains single number Q denoting number of operations Q following lines contains operations of format 1 l r p or 2 l d

Output

Print in different lines elements of array after performing all operations.

Example

Sample Input

```.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}5 8 9 12 3 5 5 1 1 5 3 2 5 9 1 1 5 3 1 2 5 2 2 3 5 ```

Sample Output

```.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}8 1 5 1 3 ```

Discussions

Show Discussion

Related Resources