Một chiếc máy ly tâm đang chứa N hạt vật chất có khối lượng khác nhau. Nhiệm vụ của chiếc máy rất đơn giản: đẩy toàn bộ các hạt có khối lượng chẵn về phía bên trái của ống nghiệm, và đẩy các hạt lẻ về phía bên phải của ống nghiệm. Bạn không cần quan tâm đến thứ tự của các hạt cùng tính chẵn lẻ ban đầu, chỉ cần chúng được chia thành hai vùng rõ rệt. Hãy mô phỏng kết quả sau khi máy ly tâm hoạt động.

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên khối lượng Ai (|Ai| <= 10^9).

Output: In ra mảng sau khi sắp xếp.

Ví dụ:

Input:

5
1 4 3 2 5

Output:

4 2 1 3 5

Công thức phối ghép một loài thực vật kỳ lạ được viết dưới dạng nén để tiết kiệm giấy: k[S] nghĩa là đoạn gen S được nhân bản k lần tiếp nối nhau. Ví dụ 3[a]2[bc] sẽ cho ra bộ gen hoàn chỉnh là aaabcbc. Các đoạn gen này thậm chí có thể chứa các đoạn nén nhỏ hơn bên trong nó. Hãy khôi phục lại bộ gen đầy đủ từ chuỗi công thức của nhà thực vật học.

Input: Xâu cần giải mã (Độ dài <= 100, độ dài xâu sau giải mã <= 10^5, ngoặc vuông luôn hợp lệ).

Output: Xâu gen sau khi giải mã.

Ví dụ:

Input:

2[ab3[c]]

Output:

abcccabccc

Trong chuỗi sự kiện thể thao đặc biệt, có N nhiệm vụ mini được đánh số từ 1 đến N, nhiệm vụ thứ i tiêu tốn của bạn T_i phút để hoàn thành. Bạn được BTC cấp cho tổng thời lượng là V phút. Để tính điểm combo, bạn phải chọn làm các nhiệm vụ liên tiếp nhau trên bảng danh sách. Chiến thuật của bạn là gì để số lượng nhiệm vụ hoàn thành được là nhiều nhất mà không bị lố thời gian?

Input:

Dòng 1: N, V (1 <= N <= 10^5, 1 <= V <= 10^9).

Dòng 2: N số nguyên Ti (1 <= Ti <= 10^4).

Output: Số lượng nhiệm vụ lớn nhất có thể hoàn thành.

Ví dụ:

Input:

4 5
3 1 2 1

Output:

3

Hai tàu thăm dò không gian đang mất kết nối với nhau do đi qua khu vực nhiễm từ. Chúng đang cố gắng phát ra các chuỗi tín hiệu cấp cứu dưới dạng hai xâu S1 và S2. Để thiết lập lại hệ thống, máy tính trên 2 tàu cần tìm ra một chuỗi mã đồng bộ là một mảng các tín hiệu giống nhau và xuất hiện cùng thứ tự trên cả 2 xâu. Tín hiệu không nhất thiết phải phát liên tiếp. Để mạng kết nối ổn định nhất, hãy giúp máy tính xác định độ dài của chuỗi mã đồng bộ dài nhất.

Input:

Dòng 1: Xâu S_1 (Độ dài <= 3000).

Dòng 2: Xâu S_2 (Độ dài <= 3000).

Output: Độ dài chuỗi mã đồng bộ dài nhất.

Ví dụ:

Input:

abcde
ace

Output:

3