You are given an array of size . You have to perform queries on the array. Each of these queries belongs to the following types of queries:
However, it is not mandatory to perform the queries in order. Your task is to determine the lexicographically largest array that can be obtained by performing all the queries.
Note:
Input format
First line: Two space-separated integers and
Next line: space-separated integers denoting the array
Next lines: The queries to be performed of the
Output format
Print space-separated integers that denote the lexicographically largest array that can be obtained as mentioned in the problem statement.
Constraints
In this case, the order in which the queries are performed does not matter. Assuming the queries are performed in the same order as the input, the array after each query is as follows:
Initially,
After query 1,
After query 2,
After query 3,
Observe that the final array would have been same even if the queries were performed in some other order.