SALT Contest (Div 2)

Hôm nay Mbappe, Morata, Bale đang solo đá bóng với nhau. Họ đều là những cầu thủ với khả năng sút bóng siêu đỉnh, bách phát bách trúng. Đá mãi với nhau mà không phân định thắng thua nên họ đã quyết định solo đá luân lưu.

Luật chơi như sau :

• Bọn họ chia bao gồm 2 đội (Do Mbappe đá luân lưu quá hay nên anh chấp hẳn mình một đội còn Morata và Bale về đội bên kia).
• Ban đầu có NN quả bóng.
• 2 đội đá luân phiên, đội của Mbappe đi trước, trong mỗi lượt đá của một đội, mỗi người chơi trong đội đó sẽ lần lượt sút một quả bóng (vì họ sút cực chuẩn nên tỉ lệ vào là 100%)
• Trò chơi kết thúc khi không còn quả bóng nào.
• Đội chiến thắng là đội sút được nhiều bóng hơn.

Cho biết số bóng ban đầu, bạn hãy dự đoán kết quả của trận đấu nhé!

Input

• Dòng đầu gồm số nguyên dương \(T\) (\(T \leq 10^5\)) là số ván đấu xảy ra

• \(T\) dòng tiếp theo, mỗi dòng là một số nguyên không âm (\(0≤N≤10^9\)) cho biết số bóng ban đầu của ván đấu tương ứng.

Output

• Gồm \(T\) dòng, dòng thứ \(i\) gồm \(1\) số nguyên là kết quả của trận đấu thứ \(i\). Xuất 1 nếu Mbappe thắng, xuất 2 nếu Mbappe thua, và xuất 0 nếu cả hai đội hòa

Example

3
3
2

2
0

Hôm nay bin9638 và algorit đánh cờ caro (dạng 3X3) với nhau, họ đánh với nhau tổng cộng n ván. Vì thắng quá nhiều nên bin9638 đã ghi lại các kết quả các ván đấu đi đem đi khoe. Mỗi tội sau đó bin9638 lại lỡ tay làm rách tờ giấy nên kết quả các trận đấu đều bị mất hết, may thay phần giấy ghi 2 nước đi đầu và người đi trước trong mỗi ván đấu thì vẫn còn.

bin9638 muốn biết ai là người thắng mỗi ván đấu nhưng ai ấy không thể xác định được, vì cả hai người đều là tuyển thủ cờ caro cấp quốc gia nên sau \(2\) nước đi đầu thì tiếp theo đó mỗi người đều sẽ đánh tối ưu. Hãy giúp bin9638 xác định nhé !

Chú ý: Người thắng là người đầu tiên đánh được \(3\) ô thẳng hàng, bất kể hàng dọc, hàng ngang hay đường chéo.

Input

• Dòng đầu tiên là số ván đấu \(Q\).
• \(Q\) dòng tiếp theo mỗi dòng lần lượt là kí tự \(ch\); tọa độ của nước đi đầu tiên \(x1,y1\); tọa độ của nước đi thứ hai \(x2,y2\) (\(ch\) là "B" nếu bin9638 đi trước, là "A" nếu algorit đi trước).

Output

• Gồm \(Q\) dòng với mỗi dòng là kết quả của ván đấu tương ứng, nếu bin9638 thắng thì ghi "B", algorit thắng thì ghi "A", còn hòa thì ghi "draw".

Constrains

• \(1 \leq Q \leq 10^5\)
• \(1 \leq x_{1},y_{1},x_{2},y_{2} \leq 3\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(Q \leq 10\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

1
B 2 2 3 2

B

Hôm nay bin9638 đang ôn thi 10.0 IELTS, đang ngồi học thì bỗng cậu thấy một gói thuốc trắng ở trên bàn nên tò mò nếm thử, không ngờ sau khi thử thì bin9638 lại thấy cơ thể nhẹ nhàng, lâng lâng và điều kì diệu là sau đó cậu có thể bay được.

Cậu ấy cứ bay lên cao, cao mãi, mãi khi tới những tầng mây thì cậu ấy gặp ông bụt ở đây. Ông bụt hứa sẽ tặng bin9638 một cuốn sách "Chinh phục 10 điểm ngữ văn" nếu cậu ấy trả lời được câu hỏi toán học của ông bụt.

Ông bụt định nghĩa một cặp số tình yêu là một cặp \(2\) số nguyên dương \(u,v\) ( \(u \le v\) ) thuộc đoạn \(l\) đến \(r\) sao cho ước chung lớn nhất của chúng không chia hết cho số nguyên dương \(n\).

Nhiệm vụ của bin9638 là đếm số lượng cặp số tình yêu với \(l\) và \(r\) cho trước. bin9638 rất muốn lấy được phần thưởng, hãy giúp cậu ấy nhé !

Input

• Dòng đầu tiên là số truy vấn \(Q\).
• \(Q\) dòng tiếp theo mỗi dòng lần lượt là \(3\) số \(l,r,n\).

Output

• Gồm \(Q\) dòng với mỗi dòng là kết quả của truy vấn tương ứng khi chia lấy dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(Q \le 10, n \le 1000, l \le r \le 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(Q \le 1000, n \le 10^3, l \le r \le 10^3\).
• Subtask \(3\) (\(40\%\) số điểm): \(Q \le 10^5, n \le 10^{18}, l \le r \le 10^{18}\).

Example

1
3 5 2

5

Chắc hẳn các bạn đã quen thuộc với giai điệu:

" Có một cái cây trong một cái vườn

Trên những tán cây nở rộ những đóa hoa

Có hai đứa nhóc đang chơi trốn tìm

Tìm hoài tìm mãi nên quên lối về "

Tuy nhiên hôm nay chúng ta không chơi trốn tìm mà là chơi xếp hình. bin9638 là một cậu bé rất thích xếp hình, hôm nay anh ấy dùng các hình lập phương nhỏ có kích thức \(1 * 1*1\) để xếp thành một hình hộp chữ nhật lớn có kích thước là các số nguyên dương \(a * b*c\).

Sau khi xếp xong thì bin9638 nhìn thấy rất nhiều hình hộp chữ nhật được tạo thành từ các hình lập phương nhỏ, anh ấy phân vân không biết tổng thể tích, tổng chu vi và tổng diện tích toàn phần của tất cả các hình hộp chữ chữ nhật phân biệt là bao nhiêu. Suy đi nghĩ lại mãi vẫn chẳng tính ra, vì vậy các bạn chuyên tin hãy tính giùm anh ấy với nhé !

Lưu ý: Hình lập phương cũng tính là hình hộp chữ nhật.

Input

• Dòng đầu tiên gồm số nguyên \(T(T \le 10^5)\).
• \(T\) dòng tiếp theo gồm \(3\) số nguyên dương \(a,b,c\).

Output

• Gồm \(T\) dòng, mỗi dòng gồm \(3\) số nguyên lần lượt là tổng thể tích, tổng chu vi, tổng diện tích toàn phần sau khi chia lấy dư cho \(10^9+7\). Điểm được tính theo số lượng đáp án mà bạn đưa ra đúng, tức là nếu số điểm của mỗi test là \(3 * C\) thì với mỗi tổng thể tích, tổng chu vi, tổng diện tích toàn phần đúng thì bạn được \(C/T\) điểm.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(a,b,c \le 10, T \le 10\).
• Subtask \(2\) (\(40\%\) số điểm): \(a,b,c \le 10^6, T \le 10^5\).
• Subtask \(3\) (\(40\%\) số điểm): \(a,b,c \le 10^{18}, T \le 10^5\).

Example

2
1 1 1
2 3 1

1 12 6
40 288 188 

Sau một chuỗi thua cá cược khi đặt hết niềm tin vào Hà Lan, Bồ Đào Nha, Pháp, Đức ... thì giờ đây algorit đã gần như mất hết tất cả, từ nhà cửa, xe cộ, sổ đỏ, tiền bạc, thậm chí cả người yêu cũng đi theo thằng khác. Có thể nói algorit bây giờ chỉ còn đúng cái nịt, nhưng với châm ngôn là còn thở còn gỡ, lần này algorit sẽ đánh cược cái nịt cuối cùng vào trận bóng tối nay.

Để khả năng cá cược thành công cao hơn thì algorit phải tính ra tỉ lệ tỉ số. Ban đầu ta có một dãy số gồm \(N\) phần tử được đánh số theo thứ tự từ \(1\) đến \(N\). Bên cạnh đó ta cũng được cung cấp một số nguyên dương \(K\leq N\).

Thực hiện lần lượt các bước sau:

• Bước 1 : Khởi tạo giá trị \(Sum := 0\)

• Bước 2 : Chọn ra một tập hợp mới, không được trùng với tập hợp nào đã chọn trước đó, gồm \(K\) số \(1 \leq i_{1} \lt i_{2} \lt i_{3} \lt ....\lt i_{k} \leq N\)

• Bước 3 : Tính giá trị \(P = a[i_{1}] * a[i_{2}] * a[i_{3}] * ........ * a[i_{k}]\)

• Bước 4 : Thực hiện tăng **Sum ** lên \(P\) (gán \(Sum:=Sum+P\))

• Bước 5 : Nếu vẫn còn tập hợp chưa được chọn thì lặp lại Bước 2, nếu không thì thực hiện Bước 6

• Bước 6 : Xuất phần dư của **Sum ** khi chia cho \(10^9+7\)

Tỉ lệ tỉ số là kết quả cuối cùng của bước \(6\), nếu tính ra tỉ lệ này thì algorit có khả năng \(99\%\) sẽ thành công trong lần cá cược này, anh sẽ giành lại những gì đã mất. Vì vậy các bạn chuyên tin hãy giúp anh ấy tìm lại sổ đỏ, tiền bạc, xe cộ nhé !

Input

• Dòng đầu tiên gồm \(2\) số nguyên dương \(N\) và \(K\).

• Dòng tiếp theo gồm \(N\) số nguyên dương \(a[i_{1}], a[i_{2}], a[i_{3}], .... , a[i_{N}] \leq 10^9\)

Output

• Gồm một số duy nhất là kết quả ở Bước 6

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(K=2\)

• Subtask \(2\) (\(10\%\) số điểm): \(K=3\)

• Subtask \(3\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 2
1 2 3 4 5

85

Hôm nay WuTan đang chơi game "Lửa chùa" với những người bạn của mình.

"Lửa chùa" là một tựa game chiến thuật, tư duy, sinh tồn đỉnh cao, không phân biệt cày chay và nạp vip, nơi mà những người bạn có những thời gian vui vẻ với nhau. Vì thấy tựa game này rất hay nên WuTan chơi suốt ngày, quên ăn quên ngủ. Lần này WuTan đang trải nghiệm chế độ mới của tựa game mang tên "Sơn tăng dame". Cụ thể trong chế độ này sẽ có \(n\) ngôi nhà được đánh số từ \(1\) đến \(n\), có \(n-1\) đường đi hai chiều nối \(2\) ngôi nhà với nhau ( đảm bảo tạo thành cây ), trong đó sẽ có \(m\) ngôi nhà đặc biệt được sơn. Để chiến thắng thì người chơi cần xóa một số ngôi nhà không được sơn ( không được xóa nhà được sơn ) sao cho không có \(2\) ngôi nhà được sơn nào có thể đi đến với nhau.

Bây giờ WuTan phân vân không biết phải xóa ít nhất bao nhiêu ngôi nhà không được sơn để có thể chiến thắng, hãy giúp cậu ấy nhé !

Input

• Dòng đầu tiên là hai số nguyên dương \(n,m\).
• \(n-1\) dòng tiếp theo mỗi dòng là \(2\) số \(u,v\) biểu thị có đường đi nối \(2\) ngôi nhà này.
• Dòng cuối cùng là dãy \(C_1,C_2,...,C_m\) biểu thị các ngôi nhà được sơn.

Output

• Gồm một số nguyên duy nhất là kết quả, nếu không tồn tại cách xóa thỏa mãn thì in ra \(-1\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m \le n \le 20\)
• Subtask \(2\) (\(20\%\) số điểm): \(m \le n \le 1000\)
• Subtask \(3\) (\(60\%\) số điểm): \(m \le n \le 5*10^5\)

Example

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

2