Linh là học sinh rất yêu thích toán học và thường nghiên cứu các bài toán về tính tổng. Hôm nay, cô giáo cho một bài toán về tính tổng nhưng Linh nghĩ mãi không tìm ra lời giải nên nhờ các bạn học sinh giỏi tin học giúp, bài toán như sau:

Cho số nguyên dương N (1 ≤ N ≤ 10^9).

Yêu cầu: Tính tổng S(N)= 1 + 2 + 3 + ... + N.

Dữ liệu vào: Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất: Nhập số nguyên dương T là số lượng test (1 ≤ T ≤ 10^5).

• T dòng tiếp theo, mỗi đòng nhập một số nguyên dương N.

Dữ liệu ra: Xuất ra màn hình gồm T dòng, mỗi dòng một số S(N) là tổng tương ứng với test đã cho.

Input:

2
3
5

Output:

6
15

Số nguyên tố là số tự nhiên lớn hơn 1 và có hai ước là một và chính nó. Một số nguyên tô được gọi là số nguyên tố "đẹp" khi nó không chứa chữ sô 3, 5 và 7. Ví dụ: các sô 2, 11, 19 là các số nguyên tố "đẹp", các số 3, 5, 7, 37, 73 không phải là số nguyên tố "đẹp".

Cho số nguyên dương N (1 ≤ N ≤ 10^6).

Yêu cầu: Đếm tất cả các số nguyên tố "đẹp" thuộc đoạn từ 1 đến N.

Dữ liệu vào: Đọc từ bàn phím số nguyên dương N.

Dữ liệu ra: Xuất ra màn hình một số nguyên dương duy nhất là số lượng số nguyên tố "đẹp".

Input:

20

Output:

3

Giải thích: Với N = 20, thì có các số nguyên tố là 2, 3, 5, 7, 11, 13, 17, 19; như vậy chỉ có 3 số nguyên tố 2, 11, 19 thỏa mãn yêu cầu bài toán.

Cho một dãy số nguyên gồm N phần tử a1,a2, ...,aN đã được sắp xếp tăng và Q truy vấn. Mỗi truy vấn gồm ba số L, R (1 ≤ L ≤ R ≤ N) và S (0 ≤ S ≤ 2*10); trong đó L và R là số nguyên dương, S là số nguyên.

Yêu cầu: Bạn hãy lập trình trả lời Q truy vấn, mỗi truy vấn yêu cầu tìm số nhỏ nhất lớn hơn hoặc bằng S thuộc đoạn L đến R (đoạn L đến R chính là dãy con liên tiếp aL, aL+1, aL+2, ..., aR).

Dữ liệu vào: Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất: Nhập hai số nguyên dương N (1 ≤ N ≤ 10^5), Q (1 ≤ Q ≤ 10^5).

• Dòng thứ hai: Nhập N số nguyên a1,a2,..., aN (0 ≤ ai ≤ 2*10^9, 1 ≤ i ≤ N).

• Q dòng tiếp theo, mỗi dòng gồm ba số nguyên L, R, S thể hiện một truy vẫn, Các số trên một dòng cách nhau một khoảng trắng.

Dữ liệu ra: Xuất ra màn hình gồm Q dòng, mỗi dòng gồm một số nguyên để trả lời câu truy vấn tương ứng. Nếu không có kết quả thì in ra -1.

Input:

5 3
2 2 8 9 10
1 3 2
1 4 7
1 5 20

Output:

2
8
-1

Giải thích:

N = 5 và dãy số có 5 phần tử là: 2, 2, 8, 9, 10.

Q - 3 nghĩa là có 3 truy vấn, gồm:

• Truy vấn 1 có kết quả là 2 vì 2 là giá trị nhỏ nhất thuộc đoạn [1, 3] thỏa mãn yêu cầu bài toán.

• Truy vấn 2 có kết quả là 8 vì 8 là giá trị nhỏ nhất thuộc đoạn [1, 4] thỏa mãn yêu cầu bài toán.

• Truy vấn 3 có kết quả là - 1 vì không có số nào nhỏ nhất thuộc đoạn [1, 5] lớn hơn hoặc bằng 20.

Tại buổi sinh hoạt ngoại khóa, các học sinh tham gia hoạt động này được chia thành N nhóm, nhóm thứ i có si (1 ≤ si ≤ 4) học sinh; nhà trường cần chuẩn bị những chiếc bàn cho hoạt động này, mỗi bàn có thể chứa tối đa 4 học sinh.

Yêu cầu: Hãy lập trình giúp Ban tổ chức chuẩn bị ít nhất bao nhiêu chiếc bàn để có thể xếp cho đủ các nhóm học sinh với điều kiện học sinh trong cùng nhóm phải ngồi cùng bàn (một bàn có thể có nhiều hơn 1 nhóm).

Dữ liệu vào: Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất: Nhập số nguyên N (1 ≤ N ≤ 10^6) là số nhóm học sinh.

• Dòng thứ hai: Nhập dãy số nguyên dương s1, s2, .., SN (1 ≤ si ≤ 4, 1 ≤ i ≤ N), si là số học sinh trong nhóm thứ i.

Các số trên một dòng cách nhau một khoảng trắng. Dữ liệu đảm bảo bài toán luôn có nghiệm.

Dữ liệu ra: Xuất ra màn hình một số nguyên dương duy nhất là số lượng bàn tối thiều cần chuẩn bị.

Input:

5
1 2 4 3 3

Output:

4