Sau một ngày dài làm việc mệt mỏi , Tuấn đã tắt điện thoại và đi ngủ. Nhưng lúc này, lại có một số người nhắn tin cho Tuấn.

Bạn hãy in ra thứ tự lần lượt từ đầu đến cuối tên các người nhắn tin cho Tuấn theo màn hình ứng dụng Messenger.

Input

Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~ là số lượng người nhắn tin cho Tuấn.

~n~ dòng tiếp theo chứa tên người nhắn tin cho Tuấn.

Đảm bảo tên mỗi người có độ dài không quá 10 kí tự và theo thứ tự thời gian tăng dần. Và đảm bảo rằng ứng dụng Messenger của Tuấn lúc đi ngủ hoàn toàn trống.

Output

Dòng đầu tiên in số nguyên ~m~ là số lượng người đã nhắn tin cho Tuấn.

~m~ dòng tiếp theo in ra tên người đã nhắn tin cho Tuấn theo thứ tự như màn hình ứng dụng Messenger.

Simple Input

8
AN
BINH
LY
AN
NHI
TINH
NHI
LY

Simple Output

5
LY
NHI
TINH
AN
BINH

Trong một cuộc thi, có ~n~ thí sinh thuộc nhiều tỉnh thành, mỗi tỉnh thành sẽ được định danh bằng một mã số. Ban tổ chức hiện tại muốn thống kê danh sách các thí sinh theo tỉnh thành để hiểu hơn về danh sách thí sinh. Họ sẽ xếp khu vực có nhiều thí sinh nhất lên trước, ít hơn sẽ để ra sau. Nếu có hai khu vực cùng số lượng thí sính, thì sẽ để khu vực có mã số nhỏ hơn lên trước và lớn hơn để ở sau.

Dựa trên nguyên tắc đã nêu, nhờ bạn hãy tìm ra xem tỉnh thành nào có nhiều thí sinh thứ tư theo cách thống kê trên, nếu không có hãy xuất ra ~-1~.

Input:

• Dòng đầu tiên chứa số nguyên dương ~n~ là số lượng thí sinh. (~ n \leq 100~)
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i~ là mã số tỉnh thành của thí sinh thứ ~i~. (~ a_i \leq 1000~)

Output:

• Một dòng duy nhất chứa mã số tỉnh thành đại diện cho khu vực xuất hiện nhiều thí sinh thứ tư trong cuộc thi.
• Nếu không có thì hãy xuất ra -1.

Sample input 1:

5
1 2 3 4 5

Sample output 1:

4

Sample input 2:

5
1 2 1 2 3

Sample output 2:

-1

Cho mảng A gồm n phần tử. Hãy cho biết có bao nhiêu đoạn con liên tiếp có tổng chia hết cho x.

Input

Dòng đầu tiên gồm 2 số n và x (~ 1 \le n \le 10^5 , 1 \le x \le 10^9 ~).

Dòng thứ hai gồm n số nguyên ~A_1, A_2, ..., A_n~ (~ 1 \le a_i \le 10^9 ~) các phần tử của mảng A.

Output

Một dòng duy nhất là số đoạn con liên tiếp có tổng chia hết cho x.

Examples

Input

6 3
5 1 2 4 3 2 

Output

9 

Giải thích: Các đoạn con liên tiếp có tổng chia hết cho 3 là:

• [1, 2]
• [1, 4]
• [1, 5]
• [2, 3]
• [2, 6]
• [3, 4]
• [3, 5]
• [4, 6]
• [5, 5]

Giới thiệu: Đây là đề Training Python 3

Nam hay sử dụng mạng xã hội để giết thời gian. Trong trang danh sách trò chuyện, khi Nam gửi tin nhắn đến một người bạn nào đó, thì cuộc trò chuyện của người bạn đó sẽ xuất hiện ở đầu trang. Thứ tự đối với các cuộc trò chuyện khác không thay đổi. Trong trường hợp nếu không có cuộc trò chuyện nào với người bạn này trước đó, thì cuộc trò chuyện mới sẽ được chèn vào đầu danh sách trò chuyện.

Giả sử rằng Nam chưa có cuộc trò chuyện nào trước đó, và Nam tạo một danh sách các cuộc trò chuyện sau khi tất cả các tin nhắn của anh ấy đã được gửi đi thành công. Giả sử không có người bạn nào nhắn bất kì tin nhắn nào cho Nam.

Input

Dòng đầu tiên chứa 1 số ~n~ ~(1 \le n \le 200 000)~ - số tin nhắn mà Nam gửi.

~n~ dòng tiếp theo hiển thị người nhận tin nhắn được sắp xếp theo thứ tự tin nhắn được gửi. Tên của mỗi người tham gia cuộc trò chuyện là một dãy kí tự gồm các chữ cái tiếng Anh viết thường có độ dài tối đa là ~10~ kí tự.

Output

In tất cả những người mà Nam đã nói chuyện theo thứ tự các cuộc trò chuyện từ trên xuống dưới.

Examples 1

Input

4
alex
ivan
roman
ivan

Output

ivan
roman
alex

Examples 2

Input

8
alina
maria
ekaterina
darya
darya
ekaterina
maria
alina

Output

alina
maria
ekaterina
darya

Note

Trong test case 1, Nam gửi tin nhắn cho bạn có tên "alex", danh sách chat của Nam sẽ hiển thị như sau:

1. alex

Sau đó Nam gửi tin nhắn cho bạn "ivan", danh sách chat của Nam sẽ hiển thị như sau:

1. ivan
2. alex

Nam gửi tin nhắn thứ 3 cho người bạn tên "roman", danh sách trò chuyện của Nam sẽ được hiển thị như sau:

1. roman
2. ivan
3. alex

Nam viết tin nhắn thứ tư cho bạn bè bằng tên "ivan", cho người mà anh ta đã gửi tin nhắn, vì vậy danh sách các cuộc trò chuyện thay đổi như sau:

1. ivan
2. roman
3. alex

Trong vùng đất H32 Da Poet.

Cáo trắng là một loại sinh vật nguy hiểm.

Vào ngày bình thường Cáo trắng ăn cắp bit của người dân để làm thức ăn. Nhưng vào những ngày trăng tròn, nếu Cáo trắng ăn cắp và ăn lượng bit có tổng trung bình là ~k~ của những dãy nhà người dân liên tục thì sức mạnh của Cáo trắng sẽ chẳng thể ngờ tới, sinh ra ảo giác và sẽ tấn công người dân. Vào lúc này nếu ai đó cho Cáo trắng một chai "vokka mâm xôi" thì nó sẽ trở lại bình thường.

Lo ngại an nguy cho các thần dân của mình. Nhà vua đã ra lệnh cho nhà toán học Lazyman tính toán xem có bao nhiêu dãy nhà liên tiếp có tổng trung bình lượng bit là ~k~ để có cách ngăn chặn con quái thú này.

Do bận với việc phải đi thực tập nên nhà toán học Lazyman đã nhờ đến bạn.

Input

Dòng đầu tiên chưa 2 số nguyên ~n~ và ~k~ ~(1 \leq k \leq 10)~ tương ứng với chiều dài và chiều rộng của vương quốc và lượng bit ~k~.

Dòng thứ hai, chứa ~n~ số nguyên ~a_1, a_2, \cdots, a_n~ ~(-10 \leq a_i \leq 10)~ là số lượng bit ở nhà dân vị tri thứ ~i~ tương ứng.

OutputFile

Số lượng dãy bit liên tiếp có tổng trung bình là ~k~.

Simple Input

6 2
1 1 2 3 1 1

Simple Output

4

Giải thích test đề:

4 dãy nhà được chọn trong testcase trên là:

• 2
• 3 1
• 1 2 3
• 2 3 1

Cách tính điểm

• Subtest 1: (~50\%~ số điểm) Với ~n = 5~.
• Subtest 2: (~20\%~ số điểm) Với ~n = 1000~.
• Subtest 3: (~30\%~ số điểm) Với ~n = 1000000~.

Problem Statement

A function ~f(x)~ defined for non-negative integers ~x~ satisfies the following conditions.

• ~f(0) = 1~ .
• ~f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)~ for any positive integer ~k~ .

Here, ~\lfloor A \rfloor~ denotes the value of ~A~ rounded down to an integer.

Find ~f(N)~ .

Constraints

• ~N~ is an integer satisfying ~0 \le N \le 10^{18}~ .

Input

The input is given from Standard Input in the following format:

~N~

Output

Print the answer.

Sample Input 1

2

Sample Output 1

3

We have ~f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3~ .

Sample Input 2

0

Sample Output 2

1

Sample Input 3

100

Sample Output 3

55

Sau mùa code camp ở Tà Nung đáng nhớ, anh Trung đã về quê của mình trồng các cây thông. Bằng phương pháp đặc biệt, anh có thể trồng được các cây xứ lạnh đó ở vùng sông nước, để cứ mỗi chiều ra ngồi bên hàng thông để ngắm hoàng hôn và chill chill code. Tuy nhiên, một ngày nọ, có một Phú ông từ phương xa đến mua mua lại hàng thông với giá cao, đem về làm đồ nội thất, vì gỗ thông rất chắc chắn. Phú ông muốn mua một dãy liên tiếp các cây thông có chiều cao trung bình là ~k~, trong đó hàng thông của anh Trung thì có ~n~ cây với chiều cao ~h_1, h_2, ..., h_n~. Anh Trung cũng không ngại bán, vì bán xong thì trồng lại cũng không khó. Vì thế anh muốn chọn một dãy dài nhất có thể các cây thông của mình để bán cho Phú ông, hỏi dãy đó sẽ bắt đầu và kết thúc tại cây nào? Bạn hãy giúp anh Trung tính toán nhé: nếu không có cách nào bán được thì in ra ~0~, còn nếu có thì in ra vị trí bắt đầu ~L~ và độ dài dài nhất đó (nếu có nhiều cách chọn thì in ra ~L~ nhỏ nhất).

Input

Dòng đầu tiên gồm số nguyên ~n,k~ với ~1 \le n \le 10^5~ và ~1 \le k \le 10^9.~

Trong cac dòng tiếp theo là độ dài của các cây thông, giá trị nguyên dương không quá ~10^9.~

Output

Đáp số của bài toán: vị trí ~L~ và độ dài.

Sample input

4 5
2
4
5
6

Sample output

2 3

Subtasks

• Sub1 (40%): ~1≤ N ≤ 500~
• Sub2 (30%): ~1≤ N ≤ 5000~
• Sub3 (30%): ~1≤ N ≤ 10^5.~

Cho đồ thị gồm n đỉnh đánh số từ 1, 2, ...n và m cạnh hai chiều nối các đỉnh.

Nhiệm vụ của bạn là cho biết số thành phần liên thông của đồ thị.

Một thành phần liên thông là một tập các đỉnh mà mỗi cặp đỉnh đều có đường đi giữa chúng.

Input

Dòng đầu tiên gồm 2 số n và m (~ 2 \le n \le 2.10^5 , 1 \le m \le 2.10^5 ~) - số đỉnh và số cạnh của đồ thị.

M dòng tiếp theo gồm 2 số u và v (~ 1 \le u, v \le n ~) - có cạnh hai chiều nối từ đỉnh u đến đỉnh v.

Output

Một dòng duy nhất là số thành phần liên thông của đồ thị.

Examples

Input

6 3 
1 2
4 1
3 5 

Output

3

Giải thích:

• Thành phần liên thông thứ nhất gồm các đỉnh 1, 2, 4

• Thành phần liên thông thứ nhất gồm các đỉnh 3, 5

• Thành phần liên thông thứ nhất gồm các đỉnh 6

CodeCamp là hoạt động thường niên của IUH hằng năm dành cho các bạn trong đội tuyển Olympic Tin Học của trường. Trong các chuyến đi CodeCamp, thầy Tình sẽ dắt các bạn trong đội tuyển đến một vùng đất mới và riêng biệt để các bạn trong đội tuyển có thể tập trung toàn bộ thời gian của mình chỉ để học code và luyện code cùng nhau.

Năm 2023, đội tuyển đã được thầy Tình cho đi CodeCamp ở Đà Lạt. Trước khi xuất phát chuyến đi, thầy Tình yêu cầu ~N~ bạn thành viên trong đội tuyển chọn cho mình một con số yêu thích, và thầy Tình sẽ cho ~2~ bạn có cùng độ tương thích về con số yêu thích sẽ ngủ cùng 1 phòng và những ai không có độ tương thích với ai cả thì sẽ ngủ ở phòng lớn.

Cụ thể, ~N~ thành viên trong đội tuyển mỗi bạn sẽ có con số yêu thích là ~A_i~ (~ 1 \leq i \leq N ~). ~2~ bạn có chỉ số ~i~ và ~j~ sẽ có cùng độ tương thích khi và chỉ khi:

• ~1 \leq i < j \leq N~
• ~A_i + A_j = 2 * lcm(A_i, A_j)~ với ~lcm(A_i, A_j)~ là bội chung nhỏ nhất của ~A_i~ và ~A_j~

Là một trong các thành viên của đội tuyển Olympic Tin Học IUH, bạn hãy giúp thầy Tình đếm trong ~N~ thành viên sẽ có bao nhiêu cặp có cùng độ tương thích nhé.

Input

Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^5~) là số lượng thành viên trong đội tuyển.

Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, A_3,... A_N~ (~1 \leq A_i \leq 10^9~) tương ứng với con số yêu thích của thành viên thứ ~i~.

Output

Xuất ra một số nguyên duy nhất là số lượng cặp các bạn sinh viên có cùng độ tương thích.

Sample Input

6
2 3 3 5 7 19022024

Sample Output

1

SubTask

• SubTask 1 (50 điểm): với ~N \leq 100~ và ~A_i \leq 100~.
• SubTask 2 (50 điểm): không có giới hạn gì thêm.

Mong ước của tớ là:

Nhìn thấy nụ cười của cậu mỗi sáng...

C có rất nhiều điều mong ước và muốn gửi gắm cho Q. Tuy nhiên, vì không muốn nói thẳng ra nên đôi khi, C mã hóa các mong ước đó lại, viết vào quyển sổ nhật ký. Chẳng hạn từ một mong ước dạng chuỗi ký tự ~s = abcd~, C có thể mã hóa thành ~s_1 = aaabccccccdd~ hoặc ~s_2 = abbbbccd~, ... nói chung là có rất nhiều cách. Tất nhiên việc mã hóa thô sơ này sẽ dẫn đến việc nhiều thông điệp khác nhau khi giải mã ngược lại có thể lại ra cùng một chuỗi (chẳng hạn ~s_1, s_2~ ở trên khi giải mã lại ra được cùng chuỗi ~s~).

Một ngày nọ, Q tình cờ đọc trộm được nhật ký của C và đọc được ~n~ điều mong muốn mà C dành cho Q. Tuy nhiên, vì có quá nhiều mong ước nên Q muốn biết rằng, trong số đó, có thực sự bao nhiêu thông điệp là đôi một khác nhau (trước khi mã hóa), hãy giúp Q tìm ra nhanh chóng điều này nhé.

Input

Dòng đầu gồm số nguyên dương ~n \le 10^5~ là số lượng mong ước đã được mã hóa, mỗi dòng tiếp theo là một chuỗi độ dài không vượt quá ~100.~

Output

Số lượng mong ước khác nhau trong đó.

Sample input 1

4
aaaaabbbbbc
abc 
aaabbbccccccccc
abcccccccc

Sample output 1

1

Sample input 2

4
iiiiillllyyyyy
tyyyyccc
tyc
illlllllllly

Sample output 2

2

Giải thích

Trong VD1, ta thấy tất cả đều xuất phát từ cùng một chuỗi ~abc~, còn trong VD2, ta có hai chuỗi là ~ily~ và ~tyc~.