Câu 1:

Để trở thành một sinh viên code giỏi bạn hãy sử dụng cấp phát vùng nhớ động (vùng nhớ heap). Viết chương trình thực hiện các yêu cầu sau:

1. Nhập m giá trị nguyên cho mảng ~A~, ~n~ giá trị nguyên cho mảng ~B (m, n > 0)~ (Các giá trị trong cùng một mảng là khác nhau và ~> 0~)

2. Tính tích các phần tử chẵn của cả ~A~ và ~B~.

3. Thực hiện phép toán giao của ~A~ và ~B~.

   

Input

Gồm 3 dòng:

• Dòng 1: Chứa 2 số nguyên ~m, n~ ~(1 ≤ m, n ≤ 1000)~.
• Dòng 2: Chứa ~m~ giá trị nguyên của mảng ~A~
• Dòng 3: Chứa ~n~ giá trị nguyên của mảng ~B~

Output

Gồm 2 dòng:

• Dòng 1: Tích của các phần tử chẵn của cả ~A~ và ~B~, nếu không có thì in ~-1~
• Dòng 2: Giao của ~A~ và ~B~ được in ra theo thứ tự tăng dần, nếu không có thì in ~-1~

Examples

Input

3 4
3 2 1
2 3 4 5

Output

16
2 3

Giải thích:

tích của các phần tử chẵn: ~2 * 2 * 4 = 16~

Phần giao là: ~2, 3~

Input

1 1
5
7

Output

-1
-1

Giải thích:

không có phần tử chẵn để tính tích nên kết quả là ~-1~

Phần giao là là rỗng nên in ~-1~

Input

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

Output

8
1 3

Câu 2:

Áp dụng những kiến thức con trỏ và cấp phát động đã học để hiểu mục đích của thuật toán dưới và bạn viết lại chương trình tương tự như vậy theo cách của bạn mà không sử dụng con trỏ và cấp phát động:

Sau khi đã kiểm tra kĩ lưỡng kết quả hãy tự tin submit code của bạn

(Lưu ý là không sử dụng con trỏ và cấp phát động, ngoài ra input và output phải giống format và kết quả với chương trình bên dưới)

Câu 3:

Mark là CEO của một công ty công nghệ và anh ấy đang cần tuyển một lập trình viên giỏi để xây dựng phần mềm quản lý thông tin các nhân viên của công ty mình.

Thông tin mỗi nhân viên gồm: mã nhân viên ~(code)~, họ tên ~(name)~, lương ~(salary)~, được khai báo như sau:

Yêu cầu của Mark như sau:

• Yêu cầu 1: Viết hàm tìm nhân viên khi biết mã nhân viên. (Hàm trả về vị trí của nhân viên nếu tìm thấy, trả về ~-1~ nếu không tìm thấy)
• Yêu cầu 2: Viết hàm xóa thông tin nhân viên khi biết mã nhân viên. (Hàm sẽ xóa thông tin nhân viên nếu tìm thấy)
• Yêu cầu 3: Viết hàm xuất các thông tin của nhân viên khi biết tên của nhân viên. (Hàm sẽ xuất thông tin nhân viên nếu tìm thấy, Xuất ~-1~ nếu không tìm thấy)

Bạn là một ứng viên tiềm năng và đang muốn ứng tuyển vào công ty của Mark, bạn hãy chứng tỏ điều đó và giải quyết bài toán này

Input

• Dòng 1: Số nguyên ~N~ ~(1 ≤ N ≤ 1000)~, số lượng nhân viên của Mark.
• ~N~ dòng tiếp theo: Thông tin của từng nhân viên theo thứ tự vị trí (mã nhân viên, tên, lương)
• Dòng tiếp theo: ~code~ của nhân viên cần tìm (để Mark test yêu cầu 1)
• Dòng tiếp theo: ~code~ của nhân viên cần xóa thông tin (để Mark test yêu cầu 2)
• Dòng cuối cùng: ~name~ của nhân viên cần xuất thông tin (để Mark test yêu cầu 3)

(Đảm bảo code và tên của mỗi nhân viên là khác nhau)

Output

Gồm 2 dòng:

• Dòng 1: vị trí của nhân viên (Kết quả của yêu cầu 1)
• Dòng 2: Thông tin của nhân viên (Kết quả của yêu cầu 3) (In ra theo format ở ví dụ dưới, salary làm tròn đến 4 chữ số thập phân)

Examples

Input

4
001 McCollum 2000
123 Saverin 1000
212 Moskovitz 1200
24532 Hughes 0
001
123
Hughes

Output

1
24532 Hughes 0.0000

Giải thích:

Vị trí của mã nhân viên ~001~ là ~1~

Sau đó xóa thông tin của Saverin

In thông tin của Chris Hughes là: 24532 Hughes 0

Input

4
001 McCollum 2000
123 Saverin 1000
212 Moskovitz 1200
24532 Hughes 0
002
123
Saverin

Output

-1
-1

Giải thích:

Không tìm thấ mã nhân viên ~002~ nên kết quả in là: ~-1~

Sau đó xóa thông tin của Saverin

Vì đã xóa thông tin của Saverin trước đó nên không còn tồn tại nhân viên này nữa và không thể xuất thông tin: ~-1~

Câu 4:

Vì bài trước bạn đã hoàn thành rất tốt nên đã được Mark tuyển vào công ty để làm việc, nhiệm vụ đầu tiên Mark giao cho bạn đó là phân tích thị trường laptop, vì công ty đang muốn lấn sân sang mảng kinh doanh này

Nhiệm vụ của bạn là thu thập thông tin của từng loại laptop đang có trên thị trường như sau:

Yêu cầu của Mark như sau:

• Yêu cầu 1: Liệt kê các tên sản phẩm của một công ty nào đó theo thứ tự xuất hiện. (Hàm trả về tên sản phẩm nếu tìm thấy công ty, trả về ~-1~ nếu không tìm thấy)
• Yêu cầu 2: Số lượng sản phẩm có cân nặng trong khoảng từ w1 đến w2. (Hàm trả về số lượng sản phẩm có cân nặng trong khoảng từ w1 đến w2)
• Yêu cầu 3: Số lượng sản phẩm có giá thấp hơn p. (Hàm trả về số lượng sản phẩm có giá thấp hơn p)
• Yêu cầu 4: Liệt kê các tên sản phẩm theo thứ tự tăng dần theo giá, nếu hai sản phẩm cùng bằng giá thì theo thứ tự giảm dần cân nặng (đảm bảo không có trường hợp cùng bằng cân nặng và giá).

Để được thăng chức thì bạn hãy giúp Mark giải quyết bài toán này

Input

• Dòng 1: Số nguyên ~N~ ~(1 ≤ N ≤ 1000)~, số lượng sản phẩm laptop.
• ~N~ dòng tiếp theo: Thông tin của từng sản phẩm (Tên, công ty, cân nặng, giá thành)
• Dòng tiếp theo: ~name~ của công ty cần tìm
• Dòng tiếp theo: 2 số nguyên ~w1, w2~ giới hạn cân nặng của laptop
• Dòng cuối: số nguyên ~p~ giá của laptop

Output

Gồm 2 dòng:

• Dòng 1: Tên các sản phẩm của công ty cần tìm theo thứ tự xuất hiện của input (Kết quả của yêu cầu 1)
• Dòng 2: Số lượng laptop có cân nặng trong khoảng ~w1->w2~ (Kết quả của yêu cầu 2)
• Dòng 3: Số lượng laptop có giá cả thấp hơn p (Kết quả yêu cầu 3)
• Dòng cuối cùng: Thứ tự sắp xếp của các sản phẩm (Kết quả yêu cầu 4)

(Tất cả in ra theo format ở ví dụ dưới)

Examples

Input

4
Legion5pro Lenovo 3 1500
MacBookAir Apple 1 2000
DellXP Dell 2 1400
MacBookPro Apple 1.5 3000
Apple
2 3
1700

Output

MacBookAir MacBookPro
2
2
DellXP Legion5pro MacBookAir MacBookPro

Giải thích:

Tên các sản phẩm của công ty Apple cần tìm theo thứ tự xuất hiện của input là: MacBookAir, MacBookPro

Có 2sp có cân nặng từ 2 đến 3 đó là: DellXP, Legion5pro

Có 2sp có giá thấp hơn 1700 đó là: DellXP, Legion5pro

Thứ tự sắp xếp như output

Input

1
Legion5pro Lenovo 3 1500
Apple
2 3
1000

Output

-1
1
0
Legion5pro

Giải thích:

Không có công ty Apple nên kết quả là: ~-1~

Có 1sp có cân nặng từ 2 đến 3 đó là: Legion5pro

Có 0sp có giá thấp hơn 1000

Thứ tự sắp xếp như output