Cho một đa giác lồi gồm \(n\) đỉnh trên hệ trục tọa độ \(OXY\). Các điểm được đánh số từ \(p_1,p_2,...,p_n\).

Với mỗi điểm \(p_i\) \((1 \le i \le n)\), hãy xác định chu vi lớn nhất của lục giác gồm các điểm trên đa giác và chứa điểm \(i\).

Input

• Dòng đầu gồm số nguyên dương \(n\).
• \(n\) dòng sau, dòng thứ \(i\) gồm \(2\) số nguyên dương \(x_i,y_i\) miêu tả tọa độ của điểm thứ \(i\). Các điểm được cho theo chiều ngược kim đồng hồ.

Output

• Gồm \(n\) dòng, dòng thứ \(i\) in ra chu vi lớn nhất của lục giác gồm các điểm trên đa giác và chứa điểm \(i\). Kết quả làm tròn đến số thứ \(4\) sau dấu phẩy.

Constraints .

• \(1 \le n \le 1000\).
• \(|x_i|,|y_i| \le 10^9\).

Subtask

• Sub \(1\) (\(30\%\)): \(n \le 10\).
• Sub \(2\) (\(30\%\)): \(n \le 100\).
• Sub \(3\) (\(40\%\)): \(n \le 1000\).

Sample Input 1

8
0 3
1 1
3 0 
6 2
5 5
3 6
1 5
5 0

Sample Output 1

27.3183
26.8052
27.3183
27.3183
27.2445
27.3183
27.3183
27.3183

Cho cây \(n\) đỉnh gồm \(n-1\) cạnh có gốc tại đỉnh \(1\). Đỉnh thứ \(i\) có giá trị là \(a_i\).

Đối với mỗi đỉnh \(u\), ta cần phải tính độ đẹp của đường đi xuất phát từ gốc là đỉnh \(1\) tới \(u\). Độ đẹp trên đường đi này được tính như sau:

• Ta có thể chọn tối đa một đỉnh \(v\) bất kì thuộc đường đi từ \(1\) tới \(u\), sau đó gán giá trị \(a_v = 0\).
• Tiếp theo, tính giá trị \(X =\) ước chung lớn nhất theo giá trị của các đỉnh thuộc đường đi từ \(1\) tới \(u\).
• Độ đẹp của đường đi từ \(1\) tới \(u\) là cách thay đỉnh tốt nhất (hoặc có thể giữ nguyên giá trị các đỉnh) sao cho giá trị \(X\) thu được là lớn nhất.

Với mỗi \(u\) từ \(1\) tới \(n\), bạn cần tính được độ đẹp của đường đi \((1,u)\), lưu ý các truy vấn ở đây là độc lập, nghĩa là bạn không thay đổi thực sự một giá trị nào cả.

Input

• Dòng đầu chứa số nguyên \(n\) \(( n \le 2 \times 10^5)\).
• Dòng tiếp theo gồm \(n\) số nguyên dương miêu tả dãy \(a\) \((1 \le a_i \le 2 \times 10^5)\)
• \(n-1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_i, v_i\) \((1≤u,v≤n; u≠v;)\) mô tả một cạnh của cây nối hai đỉnh \(u_i\) và \(v_i\).

Output

• In ra \(n\) số nguyên dương là độ đẹp của đường đi \((1,u)\) với \(u \in [1,n]\)

Subtask

• Subtask \(1\): $n \le 2000 $. \((50\%)\)
• Subtask \(2\): Không có giới hạn gì thêm. \((50\%)\)

Sample Input 1

3
6 2 3
1 2
1 3

Sample Output 1

6 6 6

Cho dãy \(n\) số nguyên \(a_1, a_2, …, a_n\) và một số nguyên \(k\). Mức độ đẹp của một dãy con liên tiếp \(a_i, a_{i+1}, …, a_j\) được đánh giá bằng \(GCD(a_i, a_{i+1}, …, a_j).(a_i + a_{i+1} + … + a_j)\), tức là độ đẹp bằng ước chung lớn nhất của các phần tử trong dãy con nhân với tổng các phần tử trong dãy con đó.

Yêu cầu: Tìm dãy con liên tiếp có ít nhất \(k\) phần tử và có mức độ đẹp là lớn nhất.

Input

• Dòng 1: Hai số nguyên \(n, k\ (1 ≤ k ≤ n ≤ 10^6)\);
• Dòng 2: \(n\) số nguyên \(a_1, a_2, …, a_n\ (1 ≤ a_i ≤ 10^6)\).

Output

• Ghi ra một số nguyên duy nhất là mức độ đẹp tìm được.

Subtask

• 10% số điểm tương ứng với 10% số test có \(n, k ≤ 100\);
• 20% số điểm tương ứng với 20% số test có \(n, k ≤ 5000\);
• 25% số điểm tương ứng với 25% số test có \(a_i ≤ 100\);
• 20% số điểm tương ứng với 20% số test có \(n, k ≤ 5.10^4\);
• 25% số điểm tương ứng với 25% số test không có ràng buộc gì thêm

Example

Sample Input

6 2
4 4 4 3 1 3

Sample Output

48

Ở một vương quốc nọ có \(n\) thành phố, được đánh số từ \(1\) đến \(n\). Mạng lưới giao thông của vương quốc gồm \(m\) con đường, con đường thứ \(i\) nối hai thành phố \(u_i\) và \(v_i\) với độ dài đúng bằng \(1\) ki-lô-mét.

Có \(k\) dự án nhà máy điện đang được triển khai, dự án thứ \(j\) sẽ xây một nhà máy điện đặt tại thành phố \(p_j\), cung cấp điện cho tất cả các thành phố nằm trong bán kính \(r_j\) ki-lô-mét (giả sử rằng quãng đường di chuyển trong nội thành là bằng \(0\)). Nhà vua đang băn khoăn, những thành phố nào đã được cấp điện, và những thành phố nào chưa được cấp điện? Hãy giúp nhà vua giải quyết bài toán này nhé.

Input

Dòng đầu chứa ba số nguyên \(n\), \(m\), \(k\) (\(2 \le n, m \le 2 \times 10^5\); \(0 \le k \le 5 \times 10^5\)).

\(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_i\), \(v_i\) (\(1 \le u_i, v_i \le n\); \(u_i \ne v_i\)) mô tả con đường thứ \(i\).

\(k\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(p_j\), \(r_j\) (\(1 \le p_j \le n\); \(0 \le r_j \le 10^9\)) mô tả dự án thứ \(j\).

Output

Gồm một dòng duy nhất chứa một xâu nhị phân gồm \(n\) kí tự, kí tự thứ \(i\) bằng "1" nếu thành phố thứ \(i\) đã được cấp điện, ngược lại kí tự thứ \(i\) bằng "0" nếu thành phố thứ \(i\) chưa được cấp điện.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n, m \le 1000\).
• Subtask \(2\) (\(30\%\) số điểm): \(r_1 = r_2 = \dots = r_{k - 1} = r_k\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

Input 1

4 3 1
1 2
1 3
2 4
2 1

Output 1

1101

Input 2

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

Output 2

101111

Có \(n\) loại đồ vật, mỗi loại có giá \(a[i]\) và số lượng tối đa \(cnt[i]\).

Bạn cần tìm cách mua hàng nhỏ thứ \(K\), trong đó:

• Một cách mua hàng là một bộ \(b[1], b[2], ..., b[n]\), với \(0 \leq b[i] \leq cnt[i]\).
• Tổng chi phí của một cách mua hàng là: \(sum_{i=1}^{n} a[i] \times b[i]\)
• Bạn sắp xếp tất cả các cách mua hàng theo chi phí tăng dần và chọn cách có chi phí nhỏ thứ \(K\).

Input

• Dòng đầu chứa hai số nguyên dương \(n, k\) (\(n, k \leq 2 \times 10^{5}\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a[i], cnt[i]\) (\(a[i] \leq 10^9, cnt[i] \leq 2 \times 10^{5}\)).

Output

• In ra chi phí của cách mua hàng nhỏ thứ \(K\).

Scoring

• Subtask 1 (20% số điểm): \(n \leq 20\).
• Subtask 2 (20% số điểm): \(n \leq 100, a[i], b[i] \leq 100\).
• Subtask 3 (20% số điểm): \(cnt[i] = 1\).
• Subtask 4 (40% số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

3 5
2 3
1 2
3 1

Output

3

Note

• Các cách mua hàng hợp lệ có chi phí sắp xếp tăng dần:
• 0: Không mua gì.
• 1: Mua 1 món loại 2 (giá 1).
• 2: Mua 2 món loại 2 (giá 2).
• 2: Mua 1 món loại 1 (giá 2).
• 3: Mua 3 món loại 2 (giá 3).
• 3: Mua 2 món loại 1 (giá 3).

• 4: Mua 1 món loại 1 và 1 món loại 2 (giá 4).

• Cách mua nhỏ thứ 5 có chi phí 3.