题目内容

塔子哥有一个长度为 $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