회사 이전

먼 나라 링크랜드에서는 IT 회사가 계속 새로 생기고 있습니다. 매주 새 회사가 세워지고, 합병되고, 인수되거나 문을 닫습니다. 링크랜드에서 이직을 준비하는 소프트웨어 엔지니어는 면접을 보는 회사의 사무실조차 찾기 어렵습니다.

이 문제를 해결하려고 새로운 IT 회사를 만듭니다. 제품은 단순합니다. 클라우드의 심층 신경 블록체인을 써서, 앱이 링크랜드 안의 임의의 두 IT 회사 사이 거리를 구합니다. 회사는 사무실을 자주 옮기고 그 변화를 따라잡기 어려우므로, 이 앱은 유용합니다. 이 정보를 한곳에 모아 세상을 더 나은 곳으로 만듭니다.

링크랜드는 하나의 직선을 따라 구성되어 있으므로, 회사의 위치는 좌표 하나로 나타납니다. 두 회사 사이의 거리는 두 좌표 사이의 거리와 같습니다.

여러분의 일은 회사의 대표 앱에 들어오는 두 종류의 요청을 처리하는 것입니다. 한 요청은 회사의 주소를 갱신합니다. 다른 요청은 두 회사 사이의 최단 거리를 묻습니다.

첫 줄에는 공백으로 구분된 두 양의 정수 $N$과 $Q$가 주어집니다. $N$은 앱이 관리하는 회사의 수($2 \le N \le 100\,000$)이고, $Q$는 처리할 요청의 수($1 \le Q \le 100\,000$)입니다.

다음 줄에는 $N$개의 정수 $X_i$($1 \le X_i \le 10^9$)가 공백으로 구분되어 주어집니다. 이는 $i=1$부터 $i=N$까지 순서대로 나열된 회사들의 초기 위치입니다.

이어지는 $Q$개의 줄 각각에는 다음 두 형식 중 하나로 정수 3개가 주어집니다.

• 1 C X: 회사 $C$가 위치를 $X$로 옮깁니다.
• 2 A B: 회사 $A$와 회사 $B$ 사이의 거리를 묻는 질의입니다.

$1 \le A, B, C \le N$과 $1 \le X \le 10^9$이 보장됩니다. 두 회사가 같은 위치에 있을 수 있습니다. 2번 형식의 질의는 적어도 하나 있습니다.

2번 형식의 각 질의에 대해, 회사 $A$와 회사 $B$ 사이의 거리를 한 줄에 출력합니다.

첫 번째 질의에서 2번 회사가 위치 10으로 옮깁니다. 이어서 4번 회사와 5번 회사 사이의 거리를 물으면 3입니다. 다음 질의는 1번 회사와 3번 회사 사이의 거리이며, 이것도 3입니다. 이후에도 갱신과 질의가 여러 번 이어집니다.