Description

You may already think Yuno is not mentally normal by this point.

However, Yuno has not been normal ever since she accidentally ## her own ##.

Yuno studied the Great Mother archetype for a long time but is still completely confused.

So she went off to make a data structure problem to farm points.

Yuno: I give you a sequence; each query asks whether a subarray is a contiguous segment on the value range.

zzy: Explain the problem statement in more detail.

Yuno: It means there cannot be duplicate numbers. For example, 1 2 2 3 is not okay, but 4 2 3 1 is okay.

yql: sb block decomposition.

ddd: sb bitset.

Yuno: Wow, you all love tree chains. I... I’ll support modifications.

zzq: ####### sb problem.

Yuno: I’m going to publish the original problem as is.

You are given a sequence $a$ of length $n$.

There are two types of operations:

1. Update the value at position $x$ to $y$.
2. Query whether the subarray $[l, r]$ can be rearranged into a consecutive range of values.

Input Format

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing $a_i$.

Each of the next $m$ lines contains three integers: either $opt$ $x$ $y$, or $opt$ $l$ $r$, representing an operation.

Output Format

If it is possible, output "damushen".

Otherwise, output "yuanxing".

5 5
1 2 3 4 5
2 1 5
2 2 3
2 3 3
1 3 4
2 3 5

damushen
damushen
damushen
yuanxing

Hint

• For $30\%$ of the testdata, $n, m \le 500$.
• For $60\%$ of the testdata, $n, m \le 100000$.
• For $100\%$ of the testdata, $n, m \le 500000$.

The initial values have value range less than $2.5 \times 10^7$. In update operations, $y \le n$. At any time, all $a_i$ are guaranteed to be positive integers.

Time limit: 2 s.

Translated by ChatGPT 5