小婷老师给小泽一个长度为 $N$ 的括号序列 $S$，其中只有圆括号、方括号和花括号。空序列合法；合法序列可以被任意同类括号包住；任意两个合法序列可以直接连接。小泽需要按这一定义判断 $S$ 是否合法。

输入格式

第一行输入 $N$，第二行输入 $S$。

输出格式

合法时输出 Valid，否则输出 Invalid。

6
))()]}

Invalid

10
(){([]{[){

Invalid

2
[(

Invalid

数据范围与约定

• $2\le N\le10^5$
• $S$ 只含 ()、[]、{} 中的字符