题目描述

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

操作一：将下标在$L$到$R$之间的元素全部或上$G$。

操作二：将下标在$L$到$R$之间的元素全部与上$G$。

操作三：将下标在$L$到$R$之间的元素全部设为$G$。

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

输入描述

第一行有一个正整数 $n(1\le n\le 10^5)$，代表数组的长度。

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

第三行有一个正整数 $m(1\le m \le 10^5)$，代表操作次数。

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

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

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

第七行有 $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