Quảng trường Nhà hát ở thủ đô Berland có hình chữ nhật với kích thước n × m mét. Nhân dịp kỷ niệm thành phố, một quyết định đã được đưa ra để lát Quảng trường bằng những viên bằng đá granit vuông. Mỗi viên đá hình vuông có kích thước a × a. Số lượng viên đá ít nhất cần thiết để lát Quảng trường là bao nhiêu? Nó được phép che phủ bề mặt lớn hơn Quảng trường Nhà hát. Nó không được phép phá vỡ các viên đá. Các cạnh của viên đá phải song song với các cạnh của Quảng trường.

Input: Đầu vào chứa ba số nguyên dương trong dòng đầu tiên: n, m và a (1 ≤ n, m, a ≤ 10^9).

Output: Viết số lượng viên đá cần thiết để lát kín quảng trường.

Ví dụ:

Input:

6 6 4

Output:

4

Đếm số cách đặt 2 con mã trên bàn cờ vua cỡ k × k với k = 1, 2, 3, .. n sao cho chúng không ăn nhau, 2 con mã này được coi là giống nhau.

Input: Số nguyên dương n duy nhất ( 1 ≤n ≤10000).

Output: Gồm n dòng, mỗi dòng là đáp án của bài toán.

Ví dụ

Input:

7

Output:

0
6
28
96
252
550
1056

Giải thích: với bàn cờ cỡ 1 x 1, không có cách nào. Với bàn cờ cỡ 2x2 có 6 cách đặt 2 con mã sao cho chúng không ăn nhau. Tương tự với các cỡ từ 3 tới 7.

Mishka là một con gấu bắc cực nhỏ. Như đã biết, những chú gấu nhỏ thích dành thời gian rảnh của mình để chơi xúc xắc cho sôcôla. Một lần vào một buổi sáng nắng tuyệt vời, đi dạo quanh những khối băng, Mishka gặp người bạn Chris của mình và họ bắt đầu chơi game. Luật chơi rất đơn giản có n vòng đấu. Trong mỗi vòng, mỗi người chơi ném một viên xí ngầu hình khối với các số khác nhau từ 1 đến 6 được viết trên mặt của nó. Người chơi, có giá trị sau khi ném xúc xắc lớn hơn sẽ thắng vòng đấu. Trong trường hợp nếu giá trị xúc xắc của người chơi bằng nhau, không ai trong số họ là người chiến thắng. Trung bình, người chơi là người chiến thắng nếu chiến thắng hầu hết các vòng. Trong trường hợp nếu hai người chơi giành được số điểm giống nhau, kết quả của trò chơi là hòa. Mishka vẫn còn rất nhỏ và không thể đếm được thắng và thua, vì vậy cô ấy yêu cầu bạn xem trận đấu của họ và xác định kết quả của nó. Xin hãy giúp cô ấy!

Input: Dòng đầu tiên chứa số nguyên n n (1 ≤ n <= 100) - số vòng chơi. Các dòng n tiếp theo chứa mô tả vòng thứ i trong số chúng chứa cặp số nguyên mi và ci (1 ≤ mi, ci ≤ 6) - các giá trị trên mặt xúc xắc sau khi Mishka và Chris 'lần lượt ném vào vòng thứ i.

Output: Nếu Mishka là người chiến thắng trong trò chơi, hãy in "Mishka" (không có dấu ngoặc kép) trong dòng duy nhất. Nếu Chris là người chiến thắng trong trò chơi, hãy in "Chris" (không có dấu ngoặc kép) trong dòng duy nhất. Nếu kết quả của trò chơi là hòa, hãy in "Friendship is magic! ^^" (không có dấu ngoặc kép) trong dòng duy nhất.

Ví dụ:

Input:

3
3 5
2 1
4 2

Output:

Mishka

Cho số nguyên dương N và hệ cơ số B. Hàm F(B,N) được định nghĩa như sau: Nếu N được biểu diễn trong hệ cơ số B có dạng:

Hãy tính giá trị hàm F với mỗi cặp B và N cho trước.

Định dạng đầu vào:

Dòng đầu ghi số lượng bộ test, không quá 1000.

Mỗi bộ test gồm 2 số nguyên: B(3≤B≤16) và số nguyên dương N (trong phạm vi số nguyên không dấu 32 bit).

Định dạng đầu ra: Với mỗi bộ test, ghi ra trên một dòng giá trị hàm F tính được.

Input:

3
10 1234
3 98765
16 987654321

Output:

30 
19 
696

Trong một cuộc bầu cử lớp trưởng, các ứng viên được đánh số. Mảng A gồm N phần tử ghi lại phiếu bầu, trong đó A[i] là mã số của ứng viên được chọn trong phiếu thứ i. Hãy tìm mã số của ứng viên nhận được nhiều phiếu bầu nhất. Nếu có nhiều người cùng số phiếu cao nhất, in ra người có mã số nhỏ nhất.

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Mã số của ứng viên chiến thắng.

Giới hạn:

1 <= N <= 10^5

1 <= A[i] <= 10^9

Ví dụ 1:

Input:

6 
1 2 2 1 3 1

Output:

1

Ví dụ 2:

Input:

4 
5 2 5 2

Output:

2

(Giải thích: 2 và 5 đều xuất hiện 2 lần, nhưng 2 nhỏ hơn 5 nên in 2)

Cho một tam giác số. Bắt đầu từ đỉnh, mỗi bước bạn có thể đi xuống ô bên trái hoặc bên phải ở hàng dưới. Hãy tìm đường đi từ đỉnh xuống đáy sao cho tổng các số đi qua là lớn nhất. Dữ liệu vào:

Dòng 1: N (số hàng).

Các dòng tiếp theo mô tả tam giác số. Dữ liệu ra:

Tổng lớn nhất. Ràng buộc:

1 <= N <= 100

Ví dụ:

Input:

3 
1 
2 3 
4 5 6

Output:

10

Giải thích: 1 -> 3 -> 6.