Cho hai số nguyên dương ~X~, ~Y~. Hãy tìm hai số nguyên dương ~A~, ~B~ thỏa mãn ~X \le A < B \le Y~ sao cho ~\gcd(A, B)~ là lớn nhất.

Input

• Gồm một dòng duy nhất gồm hai số nguyên dương ~X~, ~Y~ (~1 \le X < Y \le 2 \times 10^5~).

Output

• Gồm một dòng duy nhất là kết quả bài toán.

Example

Sample Input 1

4 7

Sample Output 1

2

Sample Input 2

19 20

Sample Output 2

1

Bạn được cho một xâu ~S~ có độ dài ~n~ gồm các chữ cái từ a đến z. Nhiệm vụ của bạn là đếm số xâu con liên tiếp mà mỗi cặp kí tự đặc biệt trong xâu con đó có khoảng cách không nhỏ hơn ~k~ (~k \le n~).

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n~, ~m~ và ~k~ ~(1 \le k \le n \le 10^5; 1 \le m \le 10)~ lần lượt là độ dài của xâu ~S~, số lượng kí tự đặc biệt và khoảng cách yêu cầu giữa hai kí tự đặc biệt bất kì.
• Dòng thứ hai chứa xâu ~S~ gồm các chữ cái từ a đến z.
• Dòng cuối cùng gồm ~m~ kí tự là các kí tự đặc biệt, dữ liệu đảm bảo ~k~ kí tự này phân biệt

Output

• Gồm một dòng duy nhất là số lượng xâu con liên tiếp thỏa mãn đề bài

Subtasks

Example

Sample Input

6 2 2
acbabc
a b

Sample Output

10

Note

Các xâu con thỏa mãn là: a, c, b, a, b, c, ac, acb, cb, bc.

Có một hàng đợi ban đầu trống. Bạn cần xử lý ~q~ truy vấn có dạng sau:

• Thêm 1 phần tử ~x~ vào cuối hàng

• Tăng giá trị các phần tử hiện tại trong hàng lên ~v~

• Xóa các phần tử có giá trị là ~x~ tại thời điểm hiện tại

Input

• Dòng đầu tiên gồm số nguyên dương ~q~ là số truy vấn (~1 \le q \le 10^5~).

• ~q~ dòng tiếp theo mỗi dòng là một truy vấn có dạng như sau:

  • ~1~ ~x~: Thêm 1 phần tử ~x~ vào cuối hàng (~1 \le x \le 10^5~).

  • ~2~ ~v~: Tăng giá trị các phần tử hiện tại trong hàng lên ~v~ (~1 \le v \le 10^5~).

  • ~3~ ~x~: Xóa các phần tử có giá trị là ~x~ tại thời điểm hiện tại (~1 \le x \le 10^5~).

Output

• Dòng đầu tiên in ra số lượng phần tử còn lại trong hàng sau ~q~ truy vấn.

• Dòng thứ hai in ra các phần tử ở trong hàng theo thứ tự từ đầu đến cuối.

Scoring

Sample Input 1

9
1 1
1 2
1 3
3 3
2 1
1 3
3 3
2 5
1 6

Sample Output 1

2
7 6

Notes

Ở test ví dụ trên:

• Sau truy vấn thứ nhất, dãy ~a = \{1\}~

• Sau truy vấn thứ hai, dãy ~a = \{1,2\}~

• Sau truy vấn thứ ba, dãy ~a = \{1,2,3\}~

• Sau truy vấn thứ tư, dãy ~a = \{1,2\}~

• Sau truy vấn thứ năm, dãy ~a = \{2,3\}~

• Sau truy vấn thứ sáu, dãy ~a = \{2,3,3\}~

• Sau truy vấn thứ bảy, dãy ~a = \{2\}~

• Sau truy vấn thứ tám, dãy ~a = \{7\}~

• Sau truy vấn cuối cùng, dãy ~a = \{7,6\}~

Hai anh em Tí và Tèo ở trên lớp được thầy giáo giao cho ~n~ bài tập về nhà, cụ thể như sau:

Có ~n~ bài tập, được đánh số từ ~1~ đến ~n~. Bài tập ~i~ thuộc loại ~t_i~.

• Nếu bài tập ~i~ được giao cho người đã hoàn thành bài tập ngay trước đó cùng loại thì thời gian thực hiện là ~b_{t_i}~.
• Nếu không, thời gian thực hiện là ~a_{t_i}~.

Mục tiêu của Tí và Tèo là phân chia công việc sao cho thời gian hoàn thành tất cả bài tập là nhanh nhẩt có thể. Các bạn hãy tính toán xem thời gian tốt nhất để hai anh em có thể hoàn thành tất cả các bài tập là bao nhiêu để hai anh em còn đi chơi.

Lưu ý:

• Bài tập phải được hoàn thành theo thứ tự đề cho.
• Trong quá trình thực hiện bài tập, không ai được nghỉ quá ~k~ bài liên tiếp.
• Mỗi bài tập chỉ cần một trong hai người hoàn thành.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n, m, k~ lần lượt là số lượng bài tập, số loại bài tập và khoảng nghỉ tối đa liên tiếp của một người (~1 \le n, m, k \le 5000~).
• Dòng thứ hai gồm ~n~ số nguyên dương ~t_1, t_2, \ldots, t_n~ là loại của của các bài tập ~(1 \le t_i \le m)~.
• Dòng thứ ba gồm ~m~ số nguyên dương ~a_1, a_2, \ldots, a_m~ là thời gian để hoàn thành công việc trong trường hợp thứ hai (~1 \le a_i \le 10^9~).
• Dòng cuối cùng gồm ~m~ số nguyên dương ~b_1, b_2, \ldots, b_m~ là thời gian để hoàn thành công việc trong trường hợp thứ nhất (~1 \le b_i \le a_i~).

Output

• Gồm một dòng là thời gian ngắn nhất để Tí và Tèo hoàn thành tất cả bài tập.

Subtasks

Example

Sample Input 1

4 3 4
1 3 1 3 
4 7 8 
2 7 7 

Sample Output 1

21

Note

• Tí sẽ làm bài tập ~1, 3~ với thời gian là ~4 + 2 = 6~.
• Tèo sẽ làm bài tập ~2, 4~ với thời gian là ~8 + 7 = 15~.

Vậy tổng thời gian ngắn nhất để Tí và Tèo hoàn thành tất cả bài tập là ~21~.

Cướp biển Aaron đang đi tìm kiếm kho báu trên Thái Bình Dương. Anh ta có một bản đồ gồm ~N~ hòn đảo được kết nối bởi một mạng lưới gồm ~M~ tuyến đường biển. Tuyến đường biển thứ ~i~ kết nối hai đảo ~a_i~ và ~b_i~ và tốn ~c_i~ đồng để di chuyển qua. Trong chuyến tìm kiếm kho báu tiếp theo, Aaron đã thăm dò từng hòn đảo và xác định rằng hòn đảo thứ ~i~ chứa một rương kho báu với ~v_i~ đồng bên trong.

Hiện anh ta cần lên kế hoạch cho chuyến hành trình tiếp theo của mình. Anh quyết định rằng anh sẽ đi qua một số (có thể là không) tuyến đường biển bắt đầu từ đảo ~x~ và kết thúc tại đảo ~y~. Khi kết thúc hành trình của mình, anh sẽ mở rương ở đảo ~y~ và thu thập số kho báu đã kiếm được.

Tuy nhiên, Aaron có một vấn đề nhỏ: anh ta không biết hiện anh ta đang ở trên đảo nào! Vì vậy, đối với mọi đảo xuất phát có thể là ~x~, anh ta muốn biết số đồng tiền tối đa mà anh ta có thể kiếm được từ tất cả các hành trình bắt đầu từ đảo ~x~. Bạn hãy giúp Aaron giải đáp thắc mắc này.

Có thể giả định rằng Aaron có đủ tiền để đi qua bất kỳ con đường biển nào mà anh ta chọn, anh ta chỉ quan tâm đến lợi nhuận ròng cuối cùng.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~M~ (~1 \le N, M \le 10^6~).
• Dòng thứ hai gồm ~N~ số nguyên dương ~v_1, v_2, ..., v_N~ (~0 \le v_i \le 10^9~).
• ~M~ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương ~a_i, b_i~ và ~c_i~ (~1 \le a_i, b_i \le n~, ~1 \le c_i \le 10^9~).

Output

• Gồm ~N~ dòng, dòng thứ ~i~ là lợi nhuận tối đa Aaron thu được khi xuất phát từ đảo thứ ~i~.

Subtasks

Example

Sample Input

4 5
6 5 9 2
1 2 0
3 2 3
4 3 6
1 3 5
2 4 2

Sample Output

6
6
9
4

Note

• Với hòn đảo thứ nhất và thứ ba, Aaron sẽ ở lại và mở rương trên chính đảo đó.
• Với hòn đảo thứ hai, Aaron sẽ đi đến hòn đảo thứ nhất và mở rương tại đó. Lợi nhuận sẽ là ~6 - 0 = 6~.
• Với hòn đảo thứ tư, Aaron sẽ đi qua hòn đảo thứ hai để đến hòn đảo thứ ba để mở rương. Lợi nhuận là ~9-2-3=4~.

Cho dãy ~a~ gồm ~n~ số nguyên dương. Hãy tìm tích của mọi ~LCM~ của các dãy con liên tiếp trong dãy ~a~. Vì kết quả có thể rất lớn, hãy in ra kết quả ~\mod{10^9 + 7}~.

Nhắc lại: ~LCM~ của một dãy là bội chung nhỏ nhất của các phần tử thuộc dãy đó.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ là số phần tử của dãy ~a~ (~1 \le n \le 2 \times 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ là các phần tử thuộc dãy ~a~ (~1 \le a_i \le n~).

Output

• Gồm một dòng duy nhất là kết quả bài toán

Subtasks

Example

Sample Input

3
2 3 1

Sample Output

648

Sample Input

4
2 4 2 4

Sample Output

262144