Contest Training K18 lần 4

Time limit: 1.0s / Memory limit: 64M

Points: 100

Cho 2 số nguyên dương n, m (Với 1 ≤ n,m ≤ 100). Và một bảng số gồm n dòng với mỗi dòng có m số. Xuất ra giá trị nhỏ nhất của mỗi cột.

Input

Dòng đầu tiên là chứa 2 số nguyên dương n, m (Với 1≤n,m≤100).

N dòng tiếp theo chứa m số nguyên dương là phần tử của bảng đó.

Output

Một dòng duy nhất chứa m số nguyên dương là giá trị nhỏ nhất của mỗi cột.

Simple Examples

Input

2 2
1 2 
3 4

Output 

1 2

Input

1 2
4 4

Output 

4 4

Input

2 1
9
6

Output 

6

Time limit: 1.0s / Memory limit: 64M

Points: 100

Cho 1 số nguyên dương n (Với 1≤n≤10000). Xuất ra bàn cờ vua có kích thước nxn - n dòng và n cột. Quân đen thì in ra 1 còn quân trăng thì in ra 0. Và ô cờ đầu tiên ở gốc trái trên có màu trắng.

Input Dòng đầu tiên là chứa 2 số nguyên dương n, n (Với 1≤n≤10000)

Output

In ra nhiều dòng là bàn cờ vua với ô đen là số 1 và ô trắng là sô 0.

Simple Examples

Input

1

Output 

0

Input

3

Output 

010
101
010

Input

9

Output 

010101010
101010101
010101010
101010101
010101010
101010101
010101010
101010101
010101010

Time limit: 2.0s / Memory limit: 256M

Points: 100

Sau số pro vjp, ta lại tiếp tục có mảng pro vjp

Bạn sẽ được cho 1 mảng a[0…n−1] có n phần tử là các số nguyên dương. Biết rằng mảng bắt đầu từ vị trí (hay còn gọi là index) 0.

Một mảng được gọi là pro vjp khi và chỉ khi với tất cả các i (0 ≤ i ≤ n−1), ta có i mod 2= a[i] mod2, biết xmod2 được tính bằng công thức x − (x/2) ∗ 2 với x là số nguyên.

Ví dụ, mảng [0,5,2,1] và [0,17,0,3] được tính là pro vjp, và mảng [2,4,6,7] là không pro vjp, bởi vì tại index i=1, mảng này đã không thỏa điều kiện trên: i mod 2 = 1 mod 2 = 1, nhưng a[i] mod 2 = 4 mod 2 = 0.

Để biến một mảng từ pro vjp, chỉ cần chọn 2 phần tử bất kì của mảng và hoán đổi vị trí của chúng (không bắt buộc 2 phần tử này phải đứng cạnh nhau). Mỗi lần hoán đổi vị trí được tính là 1 lần henshin.

Tìm số lần henshin ít nhất để mảng a hóa pro vjp, hoặc in ra -1 nếu mảng này không thể hóa pro vjp.

Input
Dòng thứ nhất chứa số nguyên t (1≤t≤1000) — là số lượng test case. Sau đấy là t test cases theo sau.

Mỗi test case có 2 dòng, dòng thứ nhất chứa số nguyên n (1≤n≤40) — là số lượng phần tử mảng a.

Dòng tiếp theo chứa n các số nguyên dương a0,a1,…,an−1 (0≤ai≤1000) — mảng a ban đầu.



Output
Mỗi test case in ra 1 số nguyên — là yêu cầu đề bài.

Examples
Input

4
4
3 2 7 6
3
3 2 6
1
7
7
4 9 2 1 18 3 0

Output

2
1
-1
0


Note
Ở test case đầu tiên, lần henshin thứ nhất, bạn đổi vị trí phần tử ở index 0 và 1, và ở lần henshin thứ hai, 2 phần tử ở index 2 và 3 sẽ được hoán đổi với nhau.

Ở test case 2, lần henshin duy nhất, hoán đổi vị trí của 2 phần tử ở index 0 và 1.

Ở test case ba, mảng này bất lực trong việc hóa pro vjp.

Time limit: 1.0s / Memory limit: 256M

Points: 100

Một số nguyên (>0) được gọi là pro vjp 2 nếu nó có dạng d00...0. Hay nói cách khác, số nguyên dương được gọi là pro vjp 2 nếu như tất cả các chữ số của nó, ngoại trừ chữ số nằm bên trái ngoài cùng, bằng 0. Cụ thể hơn, tất cả số thuộc khoảng bằng 1 to 9 là pro vjp 2.

Ví dụ, các chữ số sau đây là pro vjp 2: 4000, 1, 9, 800, 90. Còn đây thì không: 110, 707, 222, 1001.

Bạn sẽ được cho 1 số nguyên dương n n (1≤n≤~10^4~). Hãy biểu diễn số n dưới dạng các số pro vjp 2.

Input
Dòng đầu chứa 1 số nguyên t (1≤t≤~10^4~) — Số lượng test case của input. Sau đó là t test cases.

Mỗi test case là 1 dòng chứa 1 số nguyên n (1≤n≤~10^4~).

Output
In ra t test cases

Mỗi test case có 2 dòng.

Dòng thứ nhất chứa 1 số nguyên k — số lượng các số tách được.

Dòng thứ hai chứa k số, mỗi số là 1 số pro vjp 2, và tổng của chúng phải bằng n.

Lưu ý: Các số pro vjp 2 phải in theo thứ tự từ lớn đến bé

Examples
Input

5
5009
7
9876
10000
10

Output

2
5000 9
1
7 
4
9000 800 70 6
1
10000 
1
10
Time limit: 1.0s / Memory limit: 256M

Points: 100

H3.2 có tổ chức 1 hội nghị bàn tam giác. Trong hội nghị này, có một số chẵn thành viên sẽ đứng đều xung quanh 1 cái bàn hình tròn cũng đều nốt. Họ được đánh dấu từ số 1 theo chiều kim đồng hồ. Vì được sắp xếp như vậy nên chắc chắn sẽ có 1 cặp đứng đối diện nhau.

Ví dụ bàn tròn có 6 người. Mũi tên màu cam xác định xem ai đang nhìn ai. Bạn sẽ không biết có bao nhiêu người đứng trong cái bàn tròn (những ai đọc kĩ đề sẽ biết nó chắc chắn là số chẵn hehe). Bạn sẽ được cho 2 số a và b, tức là người có số a đang đứng đối diện người có số b (hoặc ngược lại). Hỏi ai đang đứng đối diện người có số d? Nếu cho 3 số a, b, và d, mà bạn thấy đề bài nó đang xạo mình thì hãy nở nụ cười thật tươi và in ra -1.

Input
Dòng đầu chứa số t (1≤t≤~10^4~) — số lượng test cases.

Ứng với mỗi test case, sẽ có 1 dòng chứa 3 số nguyên a, b, d khác nhau (1≤a,b,d≤~10^8~).

Output
Ứng với mối test case, in ra 1 dòng chứa số nguyên e — số của người đứng đối diện số d. Nếu có nhiều hơn 1 đáp án đúng thì in ra đáp án nào cũng ok hết. In ra −1 nếu nghĩ đề đang lừa mình.

Examples
Input

7
6 2 4
2 3 1
2 4 10
5 3 4
1 3 2
2 5 4
4 3 2

Output

8
-1
-1
-1
4
1
-1


Note
Cái test case đầu tiên, cái bàn tròn này có 8 người. Người có số 6 sẽ nhìn vào người có số 2 và người có số 8sẽ nhìn vào người có số 4.

Cái test case thứ hai, nếu người có số 2 đang nhìn vào người có số 3 thì hóa ra cái bàn tròn này có 2 thành viên thôi à? Nếu có 2 người kế nhau nhìn vào nhau mà trong trường hợp này thì 2 số đó chắc chắn phải là 1 và 2, vậy là đề bài đang lươn lẹo rồi.

Cái test case thứ 3, cái bàn tròn nào có người có số thứ 2 nhìn vào người có số thứ tư 4 thì không thể nào có được người có số 10. Từ đó ta suy ra, đề bài đang lươn vì người có số 10 không có tồn tại trong cái bàn này.

Time limit: 1.0s / Memory limit: 256M

Points: 100

Bỏ ngành IT, VansNhan về quê mở tiệm bán đồ ăn trưa và nuôi cá, trồng thêm rau. Cụ thể hơn, anh bán cơm trưa.

Mỗi ngày, anh chuẩn bị được a suất cơm thịt heo chiên giòn, b suất cơm cá hồi nướng và c suất cà ri bò hành tây.

Điểm đặc biệt của cái tiện này là quy trình đặt suất cơm. Do còn lậm nghề IT, nên VansNhan quyết định quy trình đặt một đơn sẽ như sau:

  • mỗi khách hàng sẽ nhận được ít nhất 1 suất cơm;
  • mỗi khách hàng sẽ không nhận được lớn hơn 1 suất cơm của cùng loại (chỉ được đặt lớn nhất 1 suất cơm thịt - - heo chiên giòn, lớn nhất 1 suất cá hồi nướng, lớn nhất 1 suất cà ri bò hành tây);
  • mỗi khách hàng sẽ nhận được các đơn khác nhau. Hỏi số lượng tối đa khách 1 ngày của VansNhan?

Input
Dòng thứ nhất chứa 1 số t (1≤t≤500) — số lượng ngày.

Tiếp theo sẽ có t dòng tương ứng với t ngày, mỗi dòng chứa 3 số nguyên a, b và c (0≤a,b,c≤10) — lần lượt là số lượng suất cơm thịt heo chiên giòn, suất cơm cá hồi nướng, suất cà ri bò hành tây VansNhan chuẩn bị của ngày hôm đó.

Output
Ứng với mỗi ngày, in ra số lượng khách tối đa của ngày hôm đó

Examples
Input

7
1 2 1
0 0 0
9 1 7
2 2 3
2 3 2
3 2 2
4 4 4

Output

3
0
4
5
5
5
7


Note
Ngày 1, VansNhan có thể cho khách 1 đơn có suất cơm thịt heo chiên giòn, khách 2 đơn có suất cơm cá hồi nướng, khách 3 đơn có cả 2 suất cá hồi nướng và cà ri bò hành tây.

Ngày 2, anh lười quá chẳng chuẩn bị gì nên chả có ma nào tới.

Ngày 3, anh có thể cho khách 1 đơn có đủ 3 suất cơm mỗi loại. Khách 2 chỉ có 1 suất cơm thịt heo chiên giòn thôi. Khách 3 sẽ có suất cơm cà ri bò hành tây, khách 4 sẽ có 1 suất thịt heo chiên giòn và 1 suất cà ri bò hành tây. Để ý thấy rằng, VansNhan chưa bán hết suất cơm của ngày hôm đó, anh chỉ có 4 khách hàng tối đa do quy trình đặt đơn này thôi.

Time limit: 2.0s / Memory limit: 256M

Points: 100

Hot boi CheeseTrung vừa đẹp trai, lại vừa giỏi lập trình nên rất được các bạn nữ thích, đặc biệt là các bạn K17. Được biết anh rất thích ăn mì, nhưng chỉ có 4 bạn biết điều đó. 4 bạn ấy đã thành lập 1 cuộc thi xem ai nấu mì giỏi nhất.

Cách thi như sau: bạn thứ nhất sẽ đấu với bạn thứ hai, 2 bạn còn lại sẽ đấu với nhau. Trong 2 cặp đấu sẽ lần lượt chọn được 2 tô mì có độ ngon nhất và sẽ được CheeseTrung ăn thử.

Độ ngon của tô mì được làm bởi bạn nữ thứ i-th sẽ bằng với si và tất cả các độ ngon của các tô mì đều khác nhau. Tô mì nào có độ ngon lớn hơn sẽ thắng.

Những hỡi ôi, CheeseTrung chỉ quan tâm tới mì thôi. Anh muốn bạn cho anh ấy biết, với cách thi đấu như vậy, thì liệu anh ấy có cơ hội để ăn 2 tô mì có độ ngon lớn nhất trong cuộc thi này không.

Xác định xem CheeseTrung có cơ hội như thế không.

Input
Dòng thứ nhất chứa 1 số nguyên t (1≤t≤~10^4~) — số lượng các test cases.

Mỗi test case chỉ chứa 1 dòng duy nhất, dòng đó chứa bốn số nguyên ~s_1~,~s_2~,~s_3~,~s_4 ~(1 ≤ ~s_i~ ≤ 100) — độ ngon của các tô mì. Biết rằng 4 số này là chắc chắn khác nhau.

Output
Mỗi test case chỉ in ra 1 từ duy nhất, YES nếu CheeseTrung có cơ hội như thế hoặc NO nếu ngược lại.

Examples
Input

4
3 7 9 5
4 5 6 9
5 3 8 1
6 5 3 2

Output

YES
NO
YES
NO

Note

  1. Trong test case 1, 2 bạn nữ thứ 2 và 3 nấu tô mì có độ ngon lần lượt là 7 và 9 và CheeseTrung đã có cơ hội để ăn;
  2. Trong test case 2, 2 bạn nữ thứ 2 và 4 nấu tô mì có độ ngon lần lượt là 5 và 9 được CheeseTrung ăn thử. Tuy nhiên đây không phải 2 tô mì có độ ngon lớn nhất cuộc thi;
Time limit: 1.0s / Memory limit: 256M

Points: 100

Trong bộ môn sinh học thời cấp 2, cấp 3 có tồn tại 1 khái niệm tên là 'nu-clê-ô-tít'

Nhà IT-học thông thái Colosuck đã sắp tìm ra được 1 loài sinh vật mới. Tuy nhiên, vì quá ngu sinh học nên anh ấy đã không biết cách hoàn thiện chuỗi nu-clê-ô-tít của nó. Anh ấy muốn bạn giúp hoàn thiện chuỗi này.

Gọi chuỗi nu-clê-ô-tít là 1 chuỗi s. Mỗi nu-clê-ô-tít trong chuỗi được đánh dấu bằng 1 chữ cái in hoa 'A', 'C', 'G' hoặc 'T'. Mỗi nu-clê-ô-tít nào không xác định được sẽ được đánh dấu '?'. Chuỗi s sẽ chứa 5 ký tự 'A', 'C', 'G', 'T' và ký tự '?'.

Biết rằng số lượng của mỗi loại nu-clê-ô-tít trong 4 loại phải bằng nhau.

Nhiệm vụ của bạn rất đơn giản, thay thế các nu-clê-ô-tít không xác định được với 1 trong 4 loại trên sao cho thỏa mãn yêu cầu của chuỗi cần tìm.

Hãy cùng Colosuck khám phá loài sinh vật mới thôi!

Input
Dòng đầu tiên chứa n (4≤n≤255) — độ dài của chuỗi nu-clê-ô-tít.

Dòng thứ hai chứa chuỗi s có độ dài n — chuỗi nu-clê-ô-tít cần được khám phá. Nó chỉ chứa 5 ký tự 'A', 'C', 'G', 'T' và '?'.

Output
Nếu chuỗi này có thể khám phá được, hãy in nó ra màn hình. Có thể in ra bất kì đáp án nào nếu có tồn tại nhiều hơn 1 chuỗi thỏa mãn yêu cầu. Nếu chuỗi này không thể khám phá được, hãy in ra dòng: "===" (bỏ dấu ngoặc).

Examples
Input

8
AG?C??CT

Output

AGACGTCT

Input

4
AGCT

Output

AGCT

Input

6
????G?

Output

===


Note
Ở ví dụ đầu tiên, Bảo đã chọn những cái hố có số lượng bi là 10 và 2, Vậy Bảo có 12 viên. Còn Trọng thì chọn cái hố có số lượng bi là 4 và 1, vậy tổng viên bi của Trọng là 5.

Time limit: 1.0s / Memory limit: 64M

Points: 100

Cho N hình chữ nhật có góc dưới bên trái là (x1, y1), góc trên bên phải là (x2, y2). Hãy tính diện tích trên mặt phẳng tọa độ bị bao phủ bởi các hình chữ nhật này.

Input

Dòng đầu tiên là số nguyên n.

N dòng tiếp theo gồm 4 số nguyên x1, y1, x2, y2 tương ứng góc dưới trái (x1, y1) và góc trên phải (x2, y2) của hình chữ nhật.

Subtask 1 (50% điểm): ~n=2, 1 ≤ x1 ≤ x2 ≤ 1000, 1 ≤ y1 ≤ y2 ≤ 1000.~

Subtask 2 (50% điểm): ~2 < n ≤ 100, 1 ≤ x1 ≤ x2 ≤ 1000, 1 ≤ y1 ≤ y2 ≤ 1000.~

Output

Một dòng duy nhất là diện tích bị bao phủ bởi các hình chữ nhật.

Examples

Input

2
1 1 4 3
2 2 5 5

Output 

13

Input 2

2
1 1 3 3
4 2 6 5

Output 2 

10