Rocky Mountain High School 的体育老师 Smith 先生喜欢在体育课上采取放任自流的教学方式。这意味着什么呢？那就是大量的躲避球运动！

在过去的几个月里，学生们一直被分成相同的两支队伍。但现在，一些学生要求做出改变。

有些学生希望被分配到特定的队伍。此外，某些目前处于对立队伍的学生之间成为了竞争对手，他们不愿意和对方在同一支队伍中。

由于 Smith 先生不想表现得过于随和，他决定重新分配队伍。他意识到，要同时满足上述两个约束条件并不一定能组成新的队伍。为了解决这个问题，他会让一些学生在下一场比赛中轮空。

你的任务是帮助 Smith 先生组成新的队伍，以满足上述约束条件，并使必须轮空的学生人数最少。注意，队伍不需要有相同数量的队员，也不要求队伍必须有队员。

输入格式

第一行包含两个整数 $N$ ($1 \le N \le 1000$)，表示学生人数；以及 $R$ ($0 \le R \le 10000$)，表示竞争关系的数量。

下一行包含一个长度为 $N$ 的字符串，描述当前队伍。该字符串由字符 A 和 B 组成。该行第 $i$ 个字符表示第 $i$ 名学生当前所在的队伍。

下一行包含一个长度为 $N$ 的字符串，描述学生要求的队伍。该字符串由字符 A、B 和 ? 组成。该行第 $i$ 个字符表示第 $i$ 名学生期望的队伍，如果学生没有偏好，则为 ?。

接下来的 $R$ 行描述竞争关系。每行包含两个不同的整数 $i$ ($1 \le i \le N$) 和 $j$ ($1 \le j \le N$)，表示学生 $i$ 和学生 $j$ 是竞争对手。竞争对手必须在不同的队伍中。没有竞争对手对会被重复报告。

输出格式

展示一个满足条件的队伍组成，使得轮空的学生人数最少。如果第 $i$ 名学生需要轮空，则第 $i$ 个字符应为 X。否则，该行的第 $i$ 个字符应为 A 或 B，表示该名学生被分配到的队伍。

如果有多种可能的解决方案，输出其中任意一种即可。

样例

输入 1

5 4
AAABB
??AAA
1 4
2 4
3 4
3 5

输出 1

BBXAA

输入 2

2 1
AB
AA
1 2

输出 2

XA

输入 3

8 8
ABBABAAA
?B?ABBAB
1 2
4 3
6 5
4 5
1 5
2 8
3 7
2 4

输出 3

BXBAXBAB