304780: CF911G. Mass Change Queries

Memory Limit:512 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Mass Change Queries

题意翻译

给出一个数列,有q个操作,每种操作是把区间[l,r]中等于x的数改成y.输出q步操作完的数列.

题目描述

You are given an array $ a $ consisting of $ n $ integers. You have to process $ q $ queries to this array; each query is given as four numbers $ l $ , $ r $ , $ x $ and $ y $ , denoting that for every $ i $ such that $ l<=i<=r $ and $ a_{i}=x $ you have to set $ a_{i} $ equal to $ y $ . Print the array after all queries are processed.

输入输出格式

输入格式


The first line contains one integer $ n $ ( $ 1<=n<=200000 $ ) — the size of array $ a $ . The second line contains $ n $ integers $ a_{1} $ , $ a_{2} $ , ..., $ a_{n} $ ( $ 1<=a_{i}<=100 $ ) — the elements of array $ a $ . The third line contains one integer $ q $ ( $ 1<=q<=200000 $ ) — the number of queries you have to process. Then $ q $ lines follow. $ i $ -th line contains four integers $ l $ , $ r $ , $ x $ and $ y $ denoting $ i $ -th query ( $ 1<=l<=r<=n $ , $ 1<=x,y<=100 $ ).

输出格式


Print $ n $ integers — elements of array $ a $ after all changes are made.

输入输出样例

输入样例 #1

5
1 2 3 4 5
3
3 5 3 5
1 5 5 1
1 5 1 5

输出样例 #1

5 2 5 4 5 

Input

题意翻译

给出一个数列,有q个操作,每种操作是把区间[l,r]中等于x的数改成y.输出q步操作完的数列.

加入题单

上一题 下一题 算法标签: