Vương quốc Alpha nổi tiếng với hệ thống giao thông thần kỳ. Vương quốc có ~N~ thành phố được đánh số từ ~1~ đến ~N~. Thành phố ~i~ được gán một giá trị gọi là năng lượng đặc trưng ~a_i~ ~(1 \le i \le N)~. Giữa hai thành phố ~u, v~ bất kỳ ~(u \ne v)~ đều có một con đường hai chiều nối trực tiếp với chi phí di chuyển là ~a_u \times a_v~.

Nhà vua muốn quản lý và cải tạo hệ thống giao thông này. Ông đã đưa ra danh sách gồm ~M~ yêu cầu, thuộc hai loại:

1. Nâng cấp thành phố: Thay đổi năng lượng của thành phố ~u~ thành giá trị mới là ~k~.

2. Truy vấn hành trình: Tính toán chi phí nhỏ nhất để đi từ thành phố ~u~ đến thành phố ~v~.

Yêu cầu: Hãy thực hiện lần lượt ~M~ yêu cầu của nhà vua, khi gặp loại truy vấn hành trình hãy đưa ra chi phí nhỏ nhất để đi từ thành phố ~u~ đến thành phố ~v~ trong truy vấn đó.

Input

• Dòng đầu tiên chứa số nguyên dương ~N, M~ ~(N, M \le 10^5)~;

• Dòng thứ hai chứa ~N~ số tự nhiên ~a_1, a_2, \dots, a_N~ ~(a_i \le 10^6)~;

• ~M~ dòng tiếp theo, mỗi dòng thể hiện một trong hai loại yêu cầu có dạng:

  • 1 u k: Thay đổi năng lượng thành phố ~u~ thành giá trị ~k~ ~(0 \le k \le 10^6)~;

  • 2 u v: Tìm chi phí nhỏ nhất để đi từ thành phố ~u~ đến thành phố ~v~ ~(1 \le u, v \le N)~.

Output

Với mỗi yêu cầu loại ~2~ (truy vấn hành trình) ghi ra một số nguyên duy nhất trên một dòng thể hiện chi phí nhỏ nhất để đi từ thành phố ~u~ đến thành phố ~v~.

Scoring

Sample Input 1

4 3
2 6 3 4
2 4 1
1 2 1
2 1 4

Sample Output 1

8
6