JUMP Contest Div 1

Hôm nay bin9638 làm thơ tình ái tặng người yêu của mình, bài thơ có dạng như sau:

"Anh sẽ why em make poem tình ái

Anh sẽ gom cloud kết thành castle

Vì castle named tình ái

Đón two đứa chúng we mà thôi

Em ơi castle tình ái that

Chắc no yes trên trần gian

Anh take em vào bằng singing

Chắp đôi wing nhung thiên thần"

algorit thấy bin9638 làm thơ quá hay, quá xuất sắc nên cũng học làm theo. Mỗi tội vì mãi code quá nhiều nên bài thơ của cậu chỉ là một xâu kí tự \(S\).

Bây giờ thay vì thơ thì algorit lại nghĩ một vấn đề liên quan đến xâu này. Một xâu con của \(S\) là một đoạn kí tự liên tiếp của nó. Ví dụ xâu TTCC thì có các xâu con là T,C,TT,TC,CC,TTC,TCC,TTCC. Bây giờ bin9638 cần tính giá trị BTS của xâu \(S\), ta có BTS(\(S\))\(= \sum_{st∈S}^{} R(st)*|st|\). Ở đây \(st\) là xâu con của \(S\), \(R(st)\) là số lần xuất hiện của nó trong \(S\), \(|st|\) là độ dài xâu \(st\).

Ví dụ với \(S\)=TTCC thì BTS\((S)\)=\(2 * 1+2*1+1*2+1*2+1*2+1*3+1*3+1*4\)=\(20\).

Input: Một dòng duy nhất là xâu \(S\) gồm các chữ cái latin viết hoa.

Output: Một dòng duy nhất là đáp án.

Ví dụ:

Input:

TTCC

Output:

20

Giới hạn:

• \(30\)% test có |\(S\)| ≤ \(500\).

• \(30\)% test có |\(S\)| ≤ \(2000\).

• \(40\)% test có |\(S\)| ≤ \(500000\).

Quốc là một sinh viên chăm chỉ, cần cù và có một cậu bạn thân tên là Phú. Trong những năm tháng quá, Quốc luôn theo đuổi một cô gái mà Phú thầm yêu. Trong một lần đi chơi cùng cô ấy thì Quốc sử dụng tiền của mình để mua quà cho cô ấy, sau đó Quốc quyết định tỏ tình nhưng cô ấy đã từ chối. Quốc về nhà với một tâm trạng buồn bã, nhưng điều mà Quốc lo lắng nhất là trong ví chỉ còn vài đồng, "làm sao sống hết tháng này đây ?". Thế là Quốc quyết định lên mạng và mở một trò chơi cho mọi người cùng tham gia.

Trò chơi có \(N\) người tham gia vào trò chơi của Quốc và người chơi có thể chọn một kí tự \(C (C = 'A'\) hoặc \(C = 'B')\), sau đó mỗi người chơi đưa ra thông số \(A_i\) và muốn đặt cược \(B_i\) đồng. Quốc cũng đưa ra một thông số nhất định \(L(0 \le |L| \le 10^9)\) (Các thông số đều là các giá trị nguyên). Quốc tưởng tượng rằng mình có thể biết trước các thông số mà người chơi đưa ra.

Trong trường hợp người chơi đưa ra kí tự \(C = 'A'\)

• Nếu thông số của người chơi đưa ra là lớn hơn hoặc bằng thông số của Quốc \((A_i \ge L)\) thì người chơi đó sẽ nhận được \(B_i\) đồng và đồng thời Quốc sẽ mất \(B_i\) đồng.
• Ngược lại, nếu thông số của người chơi đưa ra bé hơn thông số của Quốc \((A_i < L)\) thì Quốc sẽ nhận được \(B_i\) đồng và người chơi đó sẽ mất \(B_i\) đồng.

Trong người hợp người chơi đưa ra kí tự \(C = 'B'\)

• Nếu thông số của người chơi đưa ra là bé hơn hoặc bằng thông số của Quốc \((A_i \le L)\) thì người chơi đó sẽ nhận được \(B_i\) đồng và đồng thời Quốc sẽ mất \(B_i\) đồng.
• Ngược lại, nếu thông số của người chơi đưa ra lớn hơn thông số của Quốc \((A_i > L)\) thì Quốc sẽ nhận được \(B_i\) đồng và người chơi đó sẽ mất \(B_i\) đồng.

Yêu cầu : Bạn hãy chọn cho Quốc mức thông số \(L\) nhỏ nhất sao cho số tiền thu về là nhiều nhất trong trí tưởng tượng của Quốc.

Input

• Dòng đầu tiên gồm một số nguyên \(N\) là số lượng người chơi tham gia.
• \(N\) dòng tiếp theo, mỗi dòng gồm kí tự \(C\) và hai số nguyên \(A_i , B_i (1 \le B_i \le 10^9)\) lần lượt là thông số và số tiền mà người chơi thứ \(i\) muốn đặt cược.

Output

• Gồm 2 số nguyên là \(L\) và số tiền nhận được khi Quốc đưa ra thông số \(L\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(N \le 1000\) và \(0 \le |A_i| \le 1000\)
• Subtask \(2\) (\(25\%\) số điểm): \(N \le 1000\) và \(0 \le |A_i| \le 10^9\)
• Subtask \(3\) (\(25\%\) số điểm): \(N \le 10^5\) và \(0 \le |A_i|, \le 10^6\)
• Subtask \(4\) (\(25\%\) số điểm): \(N \le 2 * 10^5\) và \(0 \le |A_i|\le 10^9\)

Example

5 
A 10 30
B 3 20
A 6 10
A 5 10
B 8 20

11 10

Bé Laurier vì nghỉ dịch ở nhà nên không có gì làm, vì quá chán nản nên cô bé òa khóc. Rất may là \(2\) người thân của cô ấy (Cô Tếch và Dì Ana) tới nhà chơi và rủ Laurier đi trồng dâu.

Vườn dâu của Cô Tếch và Dì Ana là một hình chữ nhật có dạng ô lưới gồm \(a\) đường kẻ ngang và \(b\) đường kẻ dọc cách nhau \(1\) đơn vị. Các cây dâu chỉ được trồng ở các điểm giao nhau giữa các đường kẻ và bắt buộc ở ngoài viền của vườn và \(2\) cây dâu bất kì phải có khoảng cách ít nhất là \(k\) đơn vị( khoảng cách giữa \(2\) cây dâu là độ dài đoạn thẳng nối chúng ).

Bây giờ Cô Tếch và Dì Ana giao vườn dâu cho Laurier trồng. Laurier phân vân không biết mình sẽ trồng được tối đa bao nhiêu cây dâu, hãy giúp cô ấy nhé !

Input

• Một dòng duy nhất là \(3\) số nguyên dương \(a,b,k (2 \le k \le a \le b \le 2*10^9)\).

Output

• Gồm một số nguyên duy nhất là số dâu trồng được tối đa.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(k \le a \le b \le 10^5\).
• Subtask \(2\) (\(50\%\) số điểm): \(k \le a \le b \le 2*10^9\).

Example

2 3 1

6

4 4 2

4

Vào một buổi hoàng hôn, ánh nắng len lỏi qua ô cửa sổ của nhà em. Tôi đứng ngoài trời chỉ biết nhìn vào ô cửa sổ rồi mĩm cười. Trên đường về nhà, tôi cứ ngẩn ngơ vì cứ mãi suy nghĩ về em thế là tôi đã va vào một ông cụ, làm cho ông cụ bị thương. Tôi hốt hoảng, liền dẫn ông cụ đến bệnh viện để kiểm tra, cũng may là ông ấy chỉ bị trầy xước nhẹ, sau đó là lúc mà tôi phải trả tiền cho bác sĩ, tuy nhiên trong người tôi "không một xu dính túi". Ông cụ là một người cực kì giỏi toán, lúc trước ông từng là một giáo viên dạy toán xuất sắc, thế là ông đã đố tôi một bài toán và nếu giải được bài này thì tôi không cần phải trả tiền viện phí. Bài toán như sau

Ông cho một dãy số gồm \(N\) số nguyên \(A_1, A_2, A_3, ..., A_N\) và hai số nguyên \(L\) và \(R\), yêu cầu của ông là hãy chọn ra một đoạn con liên tiếp của dãy sao cho độ dài của đoạn con ít nhất là \(L\) và không quá \(R\) đồng thời có giá trị \(AVERAGE\) lớn nhất.

Giá trị \(AVERAGE\) được định nghĩa như sau: \(AVERAGE(u,v) = \frac{\sum_{i = u}^v A_i}{v - u + 1} = \frac{A_u + A_{u + 1} + ... + A_{v - 1} + A_v}{v - u + 1}\) và đảm bảo rằng \(L \le v - u +1 \le R\) \((u \le v)\).

Input

• Dòng đầu tiên là 2 số nguyên \(N, L , R\) \((1 \le L \le R \le N)\).
• Dòng thứ 2 là dãy số \(A_1, A_2, A_3, ..., A_N(|A_i| \le 10^9)\).

Output

• Gồm một số thực duy nhất là giá trị \(AVERAGE\) lớn nhất, đáp án được làm tròn đến \(4\) chữ số thập phân và chính xác đến từng chữ số.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(N \le 2000\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 2 \times 10^5\).
• Subtask \(3\) (\(20\%\) số điểm): \(N \le 10^6\).

Example

6 3 4
1 2 3 -4 6 -5

2.0000

Xuân tóc đỏ, truyền nhân của Shank tóc đỏ là một tay chơi cá cược chính hiệu. Anh luôn thắng trong những trò cá cược mình tham gia. Hôm nay đối thủ cá cược của Xuân là Phán mọc sừng.

Trò chơi này gồm một cái máy có \(n\) hộp được đánh số từ \(1\) đến \(n\) và \(n-1\) đường ống nối \(n\) những cái hộp với nhau đảm bảo tạo thành cây. Hộp \(1\) là hộp cao nhất và các hộp còn lại có độ cao giảm dần, khi thả một viên bi vào hộp \(1\) thì nó sẽ rơi dần xuống các hộp phía dưới và dừng lại khi bị chặn. Khi viên bi rơi xuống một hộp \(u\) thì xác suất viên bi rơi xuống tiếp những hộp con là như nhau ( khi viên bi rơi xuống một hộp không có hộp con thì viên bi sẽ nằm lại hộp đó).

Vì đây là một cái máy tiên tiến nên mỗi hộp đều có một vách ngăn có thể đóng mở, khi ta dùng điều khiển chọn một hộp nào đó thì nếu vách ngăn ở hộp đó mở thì nó sẽ đóng lại và ngược lại. Nếu vách ngăn ở một hộp đóng thì khi rơi viên bi sẽ bị chặn ở hộp đó, ban đầu vách ngăn ở mọi hộp đều mở.

Bây giờ Xuân sẽ thực hiện lần lượt \(q\) thao tác:

• \(1\)ㅤ\(u(1 \le u \le n):\) Tìm xác xuất để viên bi dừng lại ở hộp \(u\).

• \(2\)​​‍‍ㅤ\(u(1 \le u \le n):\) Bật tắt vách ngăn ở hộp \(u\).

Input

• Dòng đầu lần lượt là \(2\) số \(n,q\).

• \(n-1\) dòng tiếp theo mỗi dòng là \(2\) số \(u,v(u,v \le n)\) biểu thị việc có đường ống nối giữa \(2\) hộp \(u\) và \(v\).

• \(q\) dòng tiếp theo tương đương với \(q\) truy vấn.

Output

- Ứng với mỗi truy vấn loại \(1\) thì trên mỗi dòng, nếu xác suất là \(0\) thì in ra \(0\), nếu xác suất là phân số tối giản \(a/b\) (\(a,b>0\)) thì in ra \(a\) và \(b\) khi chia lấy dư cho \(10^9+7\) cách nhau một dấu cách.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le n,q \le 10^3\).
• Subtask \(2\) (\(20\%\) số điểm): \(1 \le n,q \le 5*10^5\) và không có truy vấn loại \(2\).
• Subtask \(3\) (\(50\%\) số điểm): \(1 \le n,q \le 5*10^5\).

Example

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

0
1 6
1 2
1 1
0
1 2

Cho một dãy số nguyên dương vô hạn \(A_1, A_2, ... A_N\) có một trong hai tính chất như sau (hoặc là có cả hai) :

• Tổng các chữ số của \(A_i\) chia hết cho \(m\).
• Chữ số cuối cùng của \(A_i\) là \(p(0 \le p \le 9)\).
• Và với mọi \(i > 0\) thì \(a_{i} > a_{i - 1}\).

Yêu cầu : Hãy in ra số thứ \(K\) trong dãy \(A\) và cho biết phần dư của \(\sum_{i = 1}^k A_i\) khi chia cho \(10^9 + 9\), Đề bài đảm bảo \(a_{K} \le 10^{18}\).

Input

• Dòng đầu tiên là một số nguyên dương \(T(T \le 81).\)
• \(T\) dòng tiếp theo, mỗi dòng gôm 3 số nguyên \(K,m,p\) với \((K \le 10^{18}, m \le 200, 0 \le p \le 9)\) .

Output

• Gồm \(T\) dòng, mỗi dòng gồm 2 số nguyên là đáp án của dòng truy vấn tương ứng.

Example

3
16 8 9
42 13 6
28 32 1

79 668
266 6000
271 3808