311370: CF1975G. Zimpha Fan Club

G. Zimpha Fan Clubtime limit per test12 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

One day, Zimpha casually came up with a problem. As a member of "Zimpha fan club", you decided to solve that problem.

You are given two strings $s$ and $t$ of length $n$ and $m$, respectively. Both strings only consist of lowercase English letters, - and *.

You need to replace all occurrences of * and -, observing the following rules:

• For each -, you must replace it with any lowercase English letter.
• For each *, you must replace it with a string of any (possibly, zero) length which only consists of lowercase English letters.

Note that you can replace two different instances of - with different characters. You can also replace each two different instances of * with different strings.

Suppose $s$ and $t$ have been transformed into $s'$ and $t'$. Now you're wondering if there's a replacement that makes $s'=t'$.

Input

The first line of input contains two integers $n$ and $m$ ($1 \leq n, m \leq 2 \cdot 10^6$) — the length of the strings $s$ and $t$, respectively.

The second line contains the string $s$ of length $n$. It is guaranteed that $s$ only consists of lowercase English letters, - and *.

The third line contains the string $t$ of length $m$. It is guaranteed that $t$ only consists of lowercase English letters, - and *.

Output

For each test case, output "Yes" if there is a replacement that makes $s'=t'$, and output "No" otherwise.

You can output "Yes" and "No" in any case (for example, strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive response).

ExamplesInput

10 10
justmonika
j-stsayori

Output

No

Input

7 8
ttk-wxx
*tt-l-xx

Output

Yes

Input

13 11
asoulwangziji
-soulg*z-y-

Output

No

Input

7 3
abc*cba
a*c

Output

No

Input

20 18
bulijiojio-dibuliduo
*li*ji-*ox*i*-du*-

Output

Yes

Note

In the second test case, we can transform both strings into ttklwxx. In $s$, - will be replaced with l. In $t$, * will be replaced by the empty string with the first and second - will be replaced with k and w respectively.

In the fifth test case, we can transform both strings into bulijiojioxdibuliduo.

**题目大意：**

Zimpha有一天随意提出了一个问题。作为“Zimpha粉丝俱乐部”的成员，你决定解决这个问题。

给定两个字符串s和t，分别的长度为n和m。这两个字符串仅由小写英文字母、- 和 * 组成。

你需要替换所有的 * 和 -，遵循以下规则：
- 对于每个 - ，你可以用任意一个小写英文字母替换它。
- 对于每个 * ，你可以用一个任意长度（可能为0）的仅由小写英文字母组成的字符串替换它。

注意，你可以用不同的字符替换两个不同的 -。你也可以用不同的字符串替换两个不同的 *。

假设s和t已经转换成了s'和t'。现在你想知道是否存在一种替换方式使得s'=t'。

**输入数据格式：**
- 第一行输入包含两个整数n和m（1≤n, m≤2∗106）——字符串s和t的长度。
- 第二行包含长度为n的字符串s。保证s仅由小写英文字母、- 和 * 组成。
- 第三行包含长度为m的字符串t。保证t仅由小写英文字母、- 和 * 组成。

**输出数据格式：**
- 对于每个测试用例，如果存在一种替换方式使得s'=t'，则输出"Yes"，否则输出"No"。
- 输出"Yes"和"No"时不区分大小写。**题目大意：** Zimpha有一天随意提出了一个问题。作为“Zimpha粉丝俱乐部”的成员，你决定解决这个问题。 给定两个字符串s和t，分别的长度为n和m。这两个字符串仅由小写英文字母、- 和 * 组成。 你需要替换所有的 * 和 -，遵循以下规则： - 对于每个 - ，你可以用任意一个小写英文字母替换它。 - 对于每个 * ，你可以用一个任意长度（可能为0）的仅由小写英文字母组成的字符串替换它。 注意，你可以用不同的字符替换两个不同的 -。你也可以用不同的字符串替换两个不同的 *。 假设s和t已经转换成了s'和t'。现在你想知道是否存在一种替换方式使得s'=t'。 **输入数据格式：** - 第一行输入包含两个整数n和m（1≤n, m≤2∗106）——字符串s和t的长度。 - 第二行包含长度为n的字符串s。保证s仅由小写英文字母、- 和 * 组成。 - 第三行包含长度为m的字符串t。保证t仅由小写英文字母、- 和 * 组成。 **输出数据格式：** - 对于每个测试用例，如果存在一种替换方式使得s'=t'，则输出"Yes"，否则输出"No"。 - 输出"Yes"和"No"时不区分大小写。