思路:二进制拆位 + 离线处理 + 妙用set

​ 0.这道题的一眼做法是开20个线段树，然后区间覆盖的板子。但是这里我给出一个稍微有意思的做法：这个问题的本质是可离线的序列上的区间覆盖问题

​ 1.观察到我们是所有操作都做完，最后做一次询问，而不是边操作边询问，所以可以使用离线 技巧。

题目内容

小红有一个长度为 $n$ 的数组 $arr$ ，他想玩一个游戏，这个游戏是对数组进行如下三种操作

1. 将下标在L到R之间的元素全部或上G。
2. 将下标在L到R之间的元素全部与上G。
3. 将下标在L到R之间的元素全部设为G。

现在，小红想要知道在进行 $m$ 次操作以后得到的数组，你能帮帮他吗？

输入描述

第一行有一个正整数 $n(1\leqslant n\leqslant 100000)$，代表数组的长度。

第二行有 $n$ 个非负整数，范围在$0$到 $2^{20}-1$之间，代表数组中的元素。

第三行有一个正整数 $m$ （$1\leqslant m \leqslant 100000$），代表操作次数。

第四行有 $m$ 个正整数，代表 $m$ 次操作中的区间左端点L。

第五行有 $m$ 个正整数，代表 $m$ 次操作中的区间右通点R。

第六行是一个长度为 $m$ 的字符串，'|' 代表操作1，'&' 代表操作2。'=' 代表操作3。

第七行有 $m$ 个正整数，代表 $m$ 次操作中的参数G.

输出描述

在一行中输出 $n$ 个数，代表所有操作按顺序完成后最终所得的数据。

样例

输入

4
5 4 7 4
4
1 2 3 2
4 3 4 2
=|&=
8 3 6 2

输出

8 2 2 0