SALT Contest (Div 1)

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

Hôm nay bin9638 đang đánh bài ma sói với algorit và WuTan, vì đã quá chán luật ma sói cũ nên cậu đã tự nghĩ ra luật mới.

Bộ bài ma sói gồm một số lá, gồm những lá như sau:

• Lá dân làng : được kí hiệu là "D", trong bộ bài có thể chứa nhiều lá dân làng.

• Lá ma sói: được kí hiệu là "M", trong bộ bài có thể chứa nhiều lá ma sói.

• Lá thợ săn: được kí hiệu là "T", trong bộ bài có thể chứa nhiều lá thợ săn.

• Lá phù thủy: được kí hiệu là "P", trong bộ bài có thể chứa nhiều lá phù thùy.

• Lá chiến thắng: được kí hiệu là "#", trong bộ bài chỉ chứa duy nhất MỘT lá chiến thắng.

Trong mỗi lượt chơi:

• Chỉ được rút MỘT lá ở đầu hoặc cuối bộ bài.

• Có thể sử dụng các lá bài thợ săn đang có trên tay, sau khi dùng một lá thợ săn, người chơi sẽ bỏ đồng thơi một lá thợ săn và một lá ma sói xuống (không dược bỏ lại vào bộ bài).

• Có thể sử dụng các lá bài phù thùy đang có trên tay, sau khi dùng một lá phù thùy người chơi sẽ bỏ đồng thời một lá phù thùy và một lá dân làng xuống (không được bỏ lại vào bộ bài).

• Người chơi có thể sử dụng tùy ý số lượng lá bài mình đang có, tuy nhiên chỉ được rút một lá bài duy nhất. Không nhất thiết phải làm theo thứ tự, người chơi có thể rút bài trước rồi sử dụng các lá bài, hoặc sử dụng các lá bài trước, rồi sau đó mới rút bài.

• Khi kết thúc một lượt chơi, nếu số lá ma sói người chơi đang có trên tay lớn hơn hẳn số lá dân làng người chơi đang có thì sói sẽ ăn hết dân, lúc này trò chơi kết thúc và người chơi sẽ thua cuộc.

• Người chơi sẽ chiến thắng nếu rút được lá chiến thắng.

Tuy là người đặt ra luật của trò chơi này, nhưng bin9638 không biết cách chơi như thế nào để chiến thắng, đồng thời sau khi chiến thắng, anh ấy muốn chênh lệch giữa số lá dân làng còn lại trên tay và số lá ma sói còn lại trên tay là nhỏ nhất.

Hãy giúp bin9638 chơi một cách tối ưu nhất nhé!

Input

• Dòng đầu tiên là số ván bài \(Q\).
• \(Q\) dòng tiếp theo mỗi dòng là một xâu \(S\) miêu tả bộ bài.

Input

• 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 thua thì ghi "LOSE", ngược lại ghi số lá bài chênh lệch bé nhất sau khi thắng.

Constrains

• \(Q \leq 50\)
• \(|S| \leq 2000\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(|S| \leq 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(|S| \leq 100\).
• Subtask \(3\) (\(30\%\) số điểm): \(|S| \leq 1000\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
M#DMMT
MD#DM
MM#DDDPPT
DDDP#DDDD
TPMD#MM

0
LOSE
0
2
0

Sau những trận đấu của kì euro đầy bất ngờ và kịch tính với đầy những quả miss pen và phản lưới, những trận bóng đã sút bay sổ đỏ và tiền bạc của bin9638 về nơi xa. Ngỡ như sẽ đi nhảy cầu giống như bao người anh em khác, nhưng bin9638 lại là người không dễ dàng từ bỏ. Vì vậy bin9638 đã tham gia giải cờ vua thế giới để kiếm tiền thưởng bù lại khoản lỗ.

bin9638 đánh với một bàn cờ đặc biệt gồm \(n\) hàng và \(m\) cột, ban đầu ở hàng thứ nhất anh ấy đặt một con mã ở vị trí bất kì. Mỗi nước đi con mã chỉ có thể tiến lên phía trước và đi theo hình chữ L giống như cờ vua. Giả sử con mã đang ở ô \((1;3)\) thì chỉ được đi tới ô \((2;1),(2;5),(3;2)\) hoặc \((3;4)\), ngoài ra con mã cũng không được đi ra ngoài bàn cờ. Tuy nhiên vì bàn cờ của bin9638 dùng là một bàn cờ siêu cổ, từ thời Napoleon đánh cầu lông ăn tiền nên bàn cờ có \(k\) ô đã bị hỏng, tức là không thể đặt quân cờ trên đó.

Bây giờ bin9638 muốn tính xem có bao nhiêu cách đi để đưa con mã tới hàng cuối cùng ( hàng \(n\) ), nhưng vì mải xem euro nên anh ấy đành nhờ các bạn giải giúp vậy !

Input

• Một dòng gồm 3 số nguyên dương \(n\),\(m\) và \(k\).
• \(k\) dòng tiếp theo mỗi dòng là \(2\) số nguyên dương \(x,y\) (\(x \le n, y \le m\)) biểu thị ô (\(x;y\)) đã bị hỏng.

Output

• Gồm một số duy nhất là kết quả khi chia lấy dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 10^5, m \le 50, k \le 50.\)
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 10^{18}, m \le 50, k = 0.\)
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 10^{18}, m \le 10, k \le 50.\)
• Subtask \(4\) (\(30\%\) số điểm): \(n \le 10^{18}, m \le 50, k \le 50.\)

Example

2 3 2
1 1
2 2

1

4 4 2
3 4
4 4

10