Cho số nguyên dương k và một dãy gồm N số nguyên dương ~a_1, a_2, ..., a_N~. Hãy tìm số cặp số nguyên (~l~, ~r~) với ~1 ≤ l ≤ r ≤ N~ sao cho trong đoạn con từ ~a_l~ đến ~a_r~, có tối đa một số chia hết cho ~k~.

INPUT

• Dòng 1: ~N~, ~k~ (~1 ≤ N ≤ 3×10^5~, ~1 ≤ k ≤ 10^9~)
• Dòng 2: ~a_1, a_2, ... ,a_N~ (~1 ≤ a_i ≤ 10^9~)

OUTPUT

• Một số nguyên: số lượng cặp (~l~, ~r~) thỏa mãn điều kiện.

VÍ DỤ

Input:

5 2
1 2 3 4 5

Output:

11

Cho một mảng ~a~ gồm ~n~ số nguyên, hãy tìm đoạn con liên tiếp dài đúng ~L~ có tổng lớn nhất.

• Một đoạn con dài ~L~ là [~a_i, a_{i+1}, ..., a_{i+L-1}~] với ~1 ≤ i ≤ n-L+1~
• Tính tổng lớn nhất của tất cả các đoạn con dài đúng ~L~.

Input

• Dòng 1: hai số nguyên ~n~ và ~L~ (~1 ≤ L ≤ n ≤ 2×10^5~)
• Dòng 2: mảng ~a[1] a[2] … a[n]~, mỗi phần tử ~-10^9 ≤ a[i] ≤ 10^9~

Output

• Một số nguyên: tổng lớn nhất của đoạn dài ~L~

Ví dụ

Input1:

5 3
1 2 3 1 2

Output1:

6

Giải thích:

Các đoạn dài 3:

[1,2,3] → tổng = 6

[2,3,1] → tổng = 6

[3,1,2] → tổng = 6

→ Tổng lớn nhất = 6

Cho hai xâu ký tự ~S~ và ~T~ chỉ gồm các chữ cái in hoa tiếng Anh (~A–Z~).

Hãy tìm xâu con liên tiếp ngắn nhất của ~S~ sao cho xâu con đó chứa tất cả các ký tự của ~T~, bao gồm cả số lần xuất hiện của từng ký tự.

Nếu có nhiều xâu con thỏa mãn, hãy in ra xâu có độ dài nhỏ nhất. Nếu không tồn tại, in ra xâu rỗng.

Dữ liệu vào

• Dòng 1: xâu ~S~ (~1≤∣𝑆∣≤10^5~)
• Dòng 2: xâu ~T~ (~1≤∣𝑇∣≤10^5~)

Dữ liệu ra

• In ra xâu con ngắn nhất của ~S~ thỏa mãn yêu cầu. Nếu không tồn tại, in ra xâu rỗng (không in gì)

Ví dụ

Input1:

ADOBECODEBANC
ABC

Output1:

BANC

Input2:

AAABBC
ABC

Output2:

ABBC