Relocation

In the faraway country of Lineland, tech companies keep appearing. Every week, new companies are founded, merged, acquired, or shut down. Software engineers looking for new jobs in Lineland often cannot even find the offices of the companies where they are interviewing.

To solve this, you are building a new tech company. The product is simple: using deep neural blockchains in the cloud, your app finds the distance between any two tech companies in Lineland. This is useful because companies change offices all the time, and keeping up with those moves is hard. By centralizing this information, your company will make the world a better place.

Lineland is organized around a single line, so the location of each company is a single coordinate. The distance between two companies is the distance between their two coordinates.

Your job is to handle two kinds of requests sent to the company's flagship app. One kind updates the address of a company. The other asks for the shortest distance between two companies.

The first line has two positive integers $N$ and $Q$, separated by a space. $N$ is the number of companies the app tracks ($2 \le N \le 100\,000$), and $Q$ is the number of requests to process ($1 \le Q \le 100\,000$).

The next line has $N$ integers $X_i$ ($1 \le X_i \le 10^9$), the initial locations of the companies in order from $i=1$ to $i=N$.

Each of the next $Q$ lines has three integers in one of the following forms:

• 1 C X: company $C$ moves to location $X$.
• 2 A B: a query for the distance between companies $A$ and $B$.

It is guaranteed that $1 \le A, B, C \le N$ and $1 \le X \le 10^9$. Two companies may share the same location. There is at least one query of type 2.

For each query of type 2, print the distance between companies $A$ and $B$ on its own line.

In the first query, company 2 moves to location 10. The app is then asked for the distance between company 4 and company 5, which is 3. The next query asks for the distance between companies 1 and 3, which is also 3. Several more updates and queries follow.