当前没有测试数据。

D - 范围

分数 : $400$ 分

问题描述

一个由小写英文字母、( 和 ) 组成的字符串被称为一个 好字符串，如果你可以通过以下过程将它变为空串：

• 首先，删除所有小写英文字母。
• 然后，重复删除连续的 ()。

例如，((a)ba) 是一个好字符串，因为删除所有小写英文字母后得到 (())，接着我们可以删除第 $2$ 个和第 $3$ 个字符的连续两个 ()，最终得到空串。

给定一个好字符串 $S$。 我们用 $S_i$ 表示 $S$ 的第 $i$ 个字符。

对于每一个小写英文字母 a、b、$\ldots$、z，我们有一颗写着该字母的球。 另外，我们有一个空盒子。

对于每个 $i = 1,2,$ $\ldots$ $,|S|$，高木进行以下操作，除非他晕倒。

• 如果 $S_i$ 是一个小写英文字母，则把写有该字母的球放入盒子。如果该球已经在盒子中了，他就会晕倒。
• 如果 $S_i$ 是 (，不做任何操作。
• 如果 $S_i$ 是 )，取一个整数 $j$ 小于 $i$ 且满足 $S$ 的 $j$ 到 $i$ 个字符组成一个好字符串（我们可以证明这样的整数 $j$ 总是存在）。从盒子中取出他在第 $j$ 到第 $i$ 次操作中放入的所有球。

确定高木是否可以完成这一系列操作而没有晕倒。

约束

• $1 \leq |S| \leq 3 \times 10^5$
• $S$ 是一个好字符串。

---

输入

从标准输入中按以下格式给出：

$S$

输出

如果高木可以完成这一系列操作而没有晕倒，则输出 Yes；否则输出 No。

---

((a)ba)

Yes

对于 $i = 1$，他不进行任何操作。
对于 $i = 2$，他不进行任何操作。
对于 $i = 3$，他把上面写着 a 的球放入盒子。
对于 $i = 4$，$j=2$ 是小于 $4$ 的最大整数，使得 $S$ 的第 $j$ 到第 $4$ 个字符组成一个好字符串，所以他把盒子中写着 a 的球取出来。
对于 $i = 5$，他把上面写着 b 的球放入盒子。
对于 $i = 6$，他把上面写着 a 的球放入盒子。
对于 $i = 7$，$j=1$ 是小于 $7$ 的最大整数，使得 $S$ 的第 $j$ 到第 $7$ 个字符组成一个好字符串，所以他把盒子中的球取出来，有一个是写着 a 的，另一个是写着 b 的。

因此，对于这个测试样例，答案是 Yes。

---

(a(ba))

No

对于 $i = 1$，他不进行任何操作。
对于 $i = 2$，他把上面写着 a 的球放入盒子。
对于 $i = 3$，他不进行任何操作。
对于 $i = 4$，他把上面写着 b 的球放入盒子。
对于 $i = 5$，盒子中已经有一个写着 a 的球了，所以他晕倒，中断了操作序列。

因此，对于这个测试样例，答案是 No。

---

(((())))

Yes

---

abca

No