#P0818. 咬文嚼字

咬文嚼字

题目描述

连markdownmarkdown都不会用当什么出题人?

众所周知,新生训练的所有题目都是学长学姐们一道一道出的,这其中就有许多上古老题,出的很好,但是有些题干丑的离谱,甚至还有很多数据出错的情况。

为了快速检查题目是否规范,队长使用一种特殊的处理方法将题目描述中的特殊符号和数字转化成了括号,如果这个字符串中的括号序列是合法的,这就是一道规范的题目。

合法括号序列的定义:

  • 空串合法。
  • 若AA合法,则(A)(A)合法。
  • 若AA与BB合法,则ABAB合法。

例如:序列"(())()(())()"、"()()"、"(()(()))(()(()))"是合法的,而”)()(“、"(()(()"、"(()))((()))("都不是。

但题库中题目数量太多,转化后的字符串的长度也可能很长,逐道检查费时费力,既然我们是学计算机的,为什么不让计算机来帮我们找呢?正巧新生选拔赛来临,这便成了一个检验你们学习成果的考验:

给你一批题目描述转化而成的仅由字母和左右括号组成的字符串,写程序判断这个字符串对应的题目是否规范。

输入格式

本题含有多组测试数据。

第一行输入一个正整数T(1≤T≤106)T(1 \le T \le 10^6),表示测试数据组数。

接下来对于每组测试数据,输入一行一个仅由英文字母和英文括号组成的字符串S(1≤∣S∣≤106)S(1 \le |S| \le 10^6),表示一道题目描述转化成的字符串。

题目保证:在单个测试文件中∑∣S∣≤106\sum |S| \le 10^6。

输出格式

对于每组测试数据,若括号串对应的题目规范,在一行内输出"Accepted";否则在一行内输出"Canceled"。

样例

3
(Goodmorning
(ACM)
q(w(e)r)t(y(u)i)op
Canceled
Accepted
Accepted