Cho số nguyên dương ~N~. Hãy đếm các số nguyên dương là bội của 3 hoặc 5 trong phạm vi không quá ~N~.

Input

• Dòng đầu tiên chứa số nguyên ~T~ (~1 \le T \le 10^5~) là số lượng bộ test.
• ~T~ dòng tiếp theo mỗi dòng chứa một số nguyên ~N~ (~1 \le N \le 10^{12}~).

Output

In ra ~T~ dòng, mỗi dòng chứa kết quả của một bộ test tương ứng.

Sample Input 1

3
3
5
20

Sample Output 1

1
2
9

Giải thích:

• Đoạn ~[1, 3]~ có 1 số chia hết cho 3 hoặc 5 là: 3.
• Đoạn ~[1, 5]~ có 2 số chia hết cho 3 hoặc 5 là: 3, 5.
• Đoạn ~[1, 20]~ có 9 số chia hết cho 3 hoặc 5 là: 3, 5, 6, 9, 10, 12, 15, 18, 20.

Subtasks

• Subtask 1: 80% số test có ~1 \le T \le 10^2; 1 \le N \le 10^4~.
• Subtask 2: 20% số test có ~10^2 < T \le 10^5; 10^4 < N \le 10^{12}~.

Cho hai xâu ký tự ~x~ và ~y~ cùng độ dài ~L~ (~L \le 10^5~) chỉ bao gồm các chữ cái in thường. Các ký tự được đánh số từ 1 đến ~L~. Cho ~Q~ truy vấn, mỗi truy vấn cho bởi hai số nguyên ~u, v~ lần lượt là loại truy vấn và vị trí cần truy vấn. Bạn phải trả lời các câu hỏi tương ứng với mỗi loại truy vấn như sau:

• Với truy vấn loại ~u = 1~: ký tự ở vị trí ~v~ trong chuỗi ~x~ và ~y~ có giống nhau không?
• Với truy vấn loại ~u = 2~: ký tự ở vị trí ~v~ trong chuỗi ~x~ có giống ký tự ở vị trí ánh xạ của ~v~ trong chuỗi ~y~ hay không?

Ta định nghĩa vị trí ánh xạ của ~v~ là vị trí đối xứng qua vị trí trung tâm của xâu. Ví dụ: Có hai chuỗi cùng độ dài ~L = 3~ là ~x = "lao"~, ~y = "cai"~, vị trí các ký tự được đánh số lần lượt là 1, 2, 3. Thì vị trí 3 là vị trí ánh xạ của vị trí 1 và ngược lại.

Input

• Dòng đầu tiên chứa hai chuỗi ~x, y~ cùng độ dài.
• Dòng thứ hai chứa số nguyên dương ~Q~ là số lượng truy vấn (~Q \le 10^5~).
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số ~u, v~ (~1 \le u \le 2; 1 \le v \le L~).

Output

Ghi ra ~Q~ dòng, mỗi dòng là một câu trả lời của một truy vấn tương ứng. In ra "YES" nếu hai ký tự cần so sánh giống nhau, ngược lại in ra "NO".

Sample Input 1

abc cba
1
1 2

Sample Output 1

YES

Sample Input 2

icpc cici
3
1 2
2 3
2 4

Sample Output 2

NO
NO
YES

Subtasks

• Subtask 1: 50% số test có ~Q = 1~.
• Subtask 2: 50% số test còn lại theo đúng ràng buộc của đề bài.

Tìm hai số tự nhiên ~a, b~ có tổng nhỏ nhất sao cho ước chung lớn nhất của chúng là ~c~ và bội chung nhỏ nhất của chúng là ~d~. Nếu không tồn tại ~a, b~ thỏa mãn thì in ra -1.

Input

Một dòng duy nhất chứa hai số nguyên ~c, d~ (~1 \le c, d \le 10^9~).

Output

Ghi ra tổng nhỏ nhất có thể của ~a~ và ~b~.

Sample Input 1

2 4

Sample Output 1

6

Giải thích: Chỉ có cặp ~(2, 4)~ thỏa mãn, tổng là 6.

Sample Input 2

2 12

Sample Output 2

10

Giải thích: Các cặp thỏa mãn là: ~(2, 12), (4, 6)~. Cặp ~(4, 6)~ có tổng nhỏ nhất là 10.

Sample Input 3

3 7

Sample Output 3

-1

Giải thích: Không có cặp ~(a, b)~ nào thỏa mãn.

Subtasks

• Subtask 1: 50% số test có ~1 \le c, d \le 10^9; c \times d \le 10^9~.
• Subtask 2: 50% số test có ~1 \le c, d \le 10^9; c \times d \le 10^{18}~.

Thời gian gần đây, Mỹ áp thuế đối ứng với hầu hết mặt hàng nhập khẩu vào Mỹ từ các nước khác trên thế giới, do đó cùng một mặt hàng, có thể có giá khác nhau. Công ty sản xuất gà rán KFC cần mua ~M~ đùi gà để chế biến món gà rán siêu ngon từ ~N~ nhà cung cấp khác nhau, mỗi nhà cung cấp có thể cung cấp cho KFC số lượng đùi gà và giá bán nhất định. Nhà cung cấp thứ ~i~ có thể cung cấp ~a_i~ đùi gà, mỗi đùi gà giá ~b_i~.

Cho biết KFC luôn mua được đủ số lượng đùi gà cần thiết. Hỏi số tiền ít nhất mà KFC cần bỏ ra để mua đủ số lượng đùi gà là bao nhiêu.

Input

• Dòng đầu ghi hai số ~N, M~ (~1 \le N \le 10^5, 1 \le M \le 10^9~) tương ứng với số nhà cung cấp và số lượng đùi gà cần mua.
• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ ghi hai số nguyên ~a_i, b_i~ (~1 \le a_i, b_i \le 10^9~) lần lượt là số lượng đùi gà và giá bán mỗi đùi gà của nhà cung cấp thứ ~i~.

Output

Ghi ra một số nguyên duy nhất là tổng số tiền ít nhất để mua ~M~ đùi gà từ ~N~ nhà cung cấp.

Sample Input 1

3 10
5 10
5 15
6 5

Sample Output 1

70

Giải thích: Cần mua 10 đùi gà. Có 3 nhà cung cấp. Mua 6 đùi gà của nhà cung cấp thứ 3 (giá 5) và mua 4 đùi gà của nhà cung cấp thứ 1 (giá 10). Tổng số tiền: ~6 \times 5 + 4 \times 10 = 30 + 40 = 70~.

Subtasks

• Subtask 1: 50% số test có ~N \le 10^3~.
• Subtask 2: 50% số test có ~N \le 10^5~.

Để chuẩn bị cho kỳ thi học sinh giỏi (HSG) Tin học sắp tới, thầy giáo tổ chức một đợt bồi dưỡng cho đội tuyển HSG của trường. Đội tuyển HSG có ~n~ học sinh, học sinh thứ ~i~ có kỹ năng lập trình là ~a_i~, để nâng cao kỹ năng lập trình cho học sinh trong đội tuyển, thầy giáo đã chuẩn bị ~m~ bài tập lập trình, bài tập thứ ~i~ có độ khó là ~b_i~. Học sinh thứ ~j~ có kỹ năng lập trình là ~a_j~ sau khi giải được bài tập thứ ~i~ có độ khó là ~b_i~ (với điều kiện ~a_j < b_i~) thì kỹ năng lập trình của học sinh ~j~ tăng thêm ~b_i~ đơn vị.

Yêu cầu: Cho kỹ năng lập trình ban đầu của ~n~ học sinh và độ khó của ~m~ bài tập. Hãy cho biết kỹ năng lập trình cao nhất của mỗi học sinh sau đợt bồi dưỡng. (Mỗi bài tập chỉ được giải một lần cho mỗi học sinh, và học sinh có thể giải bài tập theo thứ tự bất kỳ miễn là thỏa mãn điều kiện độ khó bài tập lớn hơn kỹ năng hiện tại).

Input

• Dòng đầu ghi 2 số nguyên dương ~n~ và ~m~ (~1 \le n, m \le 10^5~).
• Dòng thứ hai ghi ~n~ số ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~).
• Dòng thứ ba ghi ~m~ số ~b_1, b_2, ..., b_m~ (~1 \le b_i \le 10^9~).

Output

Ghi một dòng duy nhất là kỹ năng lập trình cao nhất của mỗi học sinh sau đợt bồi dưỡng, các số cách nhau một khoảng trắng.

Sample Input 1

8 7
9 37 69 17 7 3 6 75
4 15 280 21 1 27 7

Sample Output 1

84 112 144 92 82 78 81 150

Subtasks

• Subtask 1: 50% số test có ~1 \le n, m \le 10^4~.
• Subtask 2: 50% số test có ~10^4 < n, m \le 10^5~.