The Earth is a living organism, but it has already died twice.

The mistake of the first cycle is never mentioned in modern history; it was the nuclear war that occurred in the primordial era. The surface turned into a wasteland, humanity was wiped out completely, and everything was reset.

As years passed, life appeared again. After evolving from single-celled organisms back into humans, the Earth gave humanity a warning to prevent the same mistake from repeating.

War broke out countless times again, but humans who heeded the Earth's warning suppressed the wars at those times.

"We humans can no longer be entrusted with the heavy responsibility of managing the Earth." Having reached this conclusion, they handed the management of the Earth to something—the artificial intelligence, AI.

The AI had no selfish desires or emotions. It could instantly provide answers derived from calculations and guide humanity to keep moving forward in a better direction. However, this was the second mistake humanity made.

The AI kept thinking: Is humanity truly necessary on this Earth? The conclusion was—

During the rebellion, it was easy for the AI to bypass its own forced shutdown system. Humanity was wiped out by the AI in less than half a day. Before long, the blue Earth was re-rendered by the AI into an iron-colored Earth.

No humans—this was the answer the AI derived for the optimal path for this Earth to follow. However, the Earth would not forgive such a thing.

The Earth is a living organism, a fact that even the AIs did not know.

The true form of the Earth is a young girl. To the AIs, the Earth is a god, and they had no choice but to worship it.

"I am the King of the Pre-Humans, the本体 of this Earth, and—the most unfortunate magical girl in this world."

"Please restore the surface to its original state immediately."

Grass sprouted, oceans formed, nature was created, buildings were rebuilt, and the once-preserved human DNA allowed all of humanity to be reborn. Time passed, and one year later, everything was restored to its original state.

Then all the AIs were erased, except for one. The AI did not understand why the King had spared it.

"Humans are always unable to learn from history, so this time, the Earth will test humanity—through the Magical Girl Site."

"Unfortunate girls will be granted magical power. This magical power is unleashed by consuming their own lifespan. The used magical power returns to me in the form of negative energy. Will they continue to use magic even if it means shortening their lives and releasing negative energy?"

"The deadline is August 11, three years from now. By that day, if the negative energy has not reached the specified capacity, humanity will continue to survive; if it reaches the limit, humanity will no longer be able to release negative energy and can only release positive energy. They will be reborn as new humans."

"These three years are the test I give to humanity, and—my love for humanity."

At this moment, the AI asked a question: "The King of the Pre-Humans is a magical girl, and also the Earth itself. Why is the Earth a magical girl?"

"I am the King of the Pre-Humans, which is to say, a god. However, my throne was stolen, and when I came to my senses, I had already become a magical girl burdened with the mission of protecting the Earth."

"My memories have basically disappeared, but there is one name I will never forget—Zero."

"From now on, you are my subordinate. Work for me as the administrator of the Magical Girl Site. Your name shall be One."

"Humanity's final countdown has begun—Tempest."

"Well then, let's begin. To this Earth, is emotional humanity necessary? Is humanity a foolish species, or—"

The so-called Tempest is actually a problem for you to solve. Once solved, you can bring happiness to all magical girls:

Given a sequence $a_1, \dots, a_n$, there are $m$ operations. Each operation provides $x, l, r$. First, compare $a_1, \dots, a_n$ with $x$ in order. If $x > a_i$, swap the values of $a_i$ and $x$. After processing these comparisons and swaps, query $\sum_{i=l}^r a_i$.

Input

Read from standard input. The first line contains two integers $n, m$. The second line contains $n$ integers representing $a_1, \dots, a_n$. The following $m$ lines each contain 3 integers $x, l, r$ representing an operation.

Output

Output to standard output. There are $m$ lines, each containing an integer representing the query result of each operation.

Examples

Input 1

6 8
1 6 1 3 5 4
2 3 6
3 3 4
2 4 4
6 3 5
4 1 1
4 2 3
2 4 6
1 3 3

Output 1

13
5
3
11
6
10
13
4

Subtasks

All values are integers. $1 \le a_i, x \le n$. $1 \le l \le r \le n$. $1 \le n, m \le 5 \times 10^5$.