Background

Today, Kruskal-chan is again staring at the whiteboard in the club room, thinking hard.

“Hmm... walking around on a tree, and in the end returning to the starting point... does such a tree really exist?”

A junior curiously leans over. “Senpai is studying another weird problem again?”

“It’s not weird at all!” Kruskal-chan puffs out her cheeks. “This is the key problem that decides whether I can return to where I started!”

She stares at the action sequence in her hand, lightly tapping the desk with her fingers.

“If we can find such a tree, it must be very interesting~”

Problem Description

In a rooted tree $R$, the nodes are labeled with distinct positive integers. Kruskal-chan initially stays at some node of $R$. She can perform the following four actions:

• Move to the parent node, denoted by p.
• Move to any child node, denoted by c.
• Move to any sibling node with a smaller label, denoted by l.
• Move to any sibling node with a larger label, denoted by r.

Given an action sequence, determine whether there exists a rooted tree $R$ such that, by appropriately choosing the initial node and the target node of each action, Kruskal-chan can return to the initial node exactly after performing all actions.

Note: You should ensure that your construction is valid at every step. For example, if the current node is the root, then you cannot perform action p.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$ ($1\le T\le 10^5$), representing the number of test cases.

Then $T$ lines follow. Each line contains a non-empty string consisting only of the characters pclr, representing the action sequence.

It is guaranteed that the total length of all action sequences does not exceed $10^5$.

Output Format

Output $T$ lines, each representing the result for one test case. If there exists a rooted tree $R$ that satisfies the requirement, output Yes, otherwise output No.

4
l
lr
ppc
cppc

No
Yes
No
Yes

Hint

For the first and the third test cases, it can be proven that it is impossible to return to the initial node in the end.

The figure below shows a tree that satisfies the second test case. The root node is labeled $2$, and the initial node is labeled $4$. The action process can be $4\to 1\to 4$ or $4\to 3\to 4$.

The figure below shows a tree that satisfies the fourth test case. The root node is labeled $2$, and the initial node is labeled $1$. The action process is $1\to 4\to 1\to 2\to 1$.

Translated by ChatGPT 5