Happy New Year

Hân thích học những thuật toán đỉnh cao và mã hóa là một thuật toán như vậy. Ngày nọ, Hân nghĩ ra thuật toán mã hóa của riêng mình: Mỗi chuỗi sẽ quy về số kí tự có trong chuỗi đó. Cho một dãy gồm các chuỗi kí tự và cách nhau bởi dấu cách. Hãy áp dụng thuật toán của Hân để mã hóa dãy kí tự đã cho.

Input

• Một dòng duy nhất gồm các chuỗi kí tự

Output

• In ra một dãy số là dãy mã hóa của các chuỗi kí tự.

Constraints

• Số lượng chuỗi được cho \(\leq 10\)

Example

Happy New Year 2021

5 3 4 4

Le Cong Quoc Han

2 4 4 3

Quý rất thích làm toán, nên đã thách đố bạn bài sau: Cho số tự nhiên \(n\), hãy tính tổng \(1-2+3-4+\dots n\).

Input

• Dòng đầu tiên và duy nhất chứa 1 số tự nhiên \(n\).

Output

• In ra một số nguyên là đáp số của tổng trên.

Constraints

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 10^6\)
• Subtask \(2\) (\(50\%\) số điểm): \(n \leq 10^9\)

Example

4

-2

5

3

Bảo Anh là em họ của Anh Kha, và cậu rất thích những điều siêu to khổng lồ. Sau khi đạt được một số điểm siêu to khổng lồ trong kì thi chọn Học Sinh Giỏi của hành tinh Trái Nước, Bảo Anh được đại ca ami tặng một dãy số siêu to khổng lồ.

Dãy số được cho gồm \(N\) phần tử \(a_1, a_2, \dots, a_n\). Cảm thấy vẫn chưa xứng đáng với thành tích của mình, Bảo Anh muốn ami tặng thêm một số \(X\) siêu to nữa.

Vẫn chưa cảm thấy đủ, Bảo Anh quyết định tìm một số \(Y \geq X\) nhỏ nhất mà \(Y\) chia hết cho một số bất kì trong dãy \(a\) vì cậu nghĩ số này là một số siêu to khổng lồ.

Input

• Dòng đầu tiên chứa hai số \(N, X\)
• Dòng thứ hai chứa dãy \(a\), gồm \(N\) số nguyên dương \(a_1, a_2, \dots, a_n\)

Output

• In ra một số nguyên duy nhất là đáp án bài toán

Constraints

• \(1 \leq n \leq 10^5\)
• \(0 \leq x \leq 10^{18}\)
• \(1 \leq a_i \leq 10^{18}\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 100, a_i \leq 10^4, x \leq 2*10^4\)
• Subtask \(2\) (\(20\%\) số điểm): \(a_i \leq 10^6, x \leq 2*10^6\)
• Subtask \(3\) (\(30\%\) số điểm): Không có điều kiện gì thêm

3 5
2 3 4

6

Đức rất thích cống. Nhận thấy sở thích này rất bất thường và không sạch sẽ, ami quyết định bày Đức một trò chơi liên quan đến số học.

ami cho Đức 4 số \(c,u,o,m\). Đức có thể chọn một trong 3 số \(u, o, m\) và chia \(c\) cho số được chọn. Đức có thể lặp lại thao tác trên với số lần vô hạn nếu cậu thích, mục tiêu là làm cho số \(c\) trở thành \(1\). Tuy không thích số học, nhưng lại không dám làm trái lời ami, Đức muốn nhờ các bạn tìm ra số thao tác ít nhất để biến \(c\) thành \(1\), hoặc báo cho Đức là không thể, để Đức còn có thời gian đi chơi với cống.

Input

• Dòng đầu tiên chứa \(t\) là số câu hỏi.
• \(t\) câu hỏi có dạng như sau: Dòng đầu tiên của mỗi câu hỏi chứa 1 số nguyên \(c\), dòng thứ hai chứa 3 số nguyên \(u, o, m\).

Output

• Với mỗi câu hỏi, hãy in ra số thao tác ít nhất cần dùng để biến \(c\) thành \(1\) hoặc in ra \(−1\) nếu không tồn tại bất kì cách làm nào.

Scoring

Trong tất cả các test, \(1 \leq c,u,o,m \leq 10^{18}\)

• Subtask \(1\) (\(40\%\) số điểm): \(t=1, u=o=m\)
• Subtask \(2\) (\(20\%\) số điểm): \(t \leq 100\), \(u,o,m\) đôi một nguyên tố cùng nhau
• Subtask \(3\) (\(20\%\) số điểm): \(t \leq 100, u=o\)
• Subtask \(4\) (\(20\%\) số điểm): \(t \leq 100\)

Example

3
6
1 2 3
7
1 2 7
8
4 4 4

2
1
-1

Anh Kha và cuom1999 là một cặp huynh đệ đồng môn dưới sự chỉ dạy của sư phự ami ở bộ môn Liên Minh of Legend. Anh Kha đã lĩnh hội thành công phương thức gánh team bằng giao thức Apeliot. cuom1999 rất ghen tị. Sau một trận đấu có KDA 1/9/2, cuom1999 quyết định nhờ Anh Kha chỉ dạy bí thuật Apeliot cho mình.

Anh Kha là một thiếu niên nghiêm túc và đầy lòng trắc ẩn. Cậu nhận thấy rằng nếu chỉ đơn giản đưa bí kíp cho cuom1999, cuom1999 sẽ không thể nhớ được. Vì vậy, mỗi lần truyền thụ một bí kíp, Anh Kha sẽ đưa cho cuom1999 một xâu kí tự \(S\) chỉ chứa các kí tự trong tập {c , u , o , m , g , a , v , l}, cuom1999 sẽ thêm một kí tự cũng thuộc tập trên vào một vị trí bất kì trong xâu \(S\) sao cho số lượng xâu kí tự \(cu\) xuất hiện trong xâu \(S\) sau khi thêm là nhiều nhất. Số lượng kí tự \(cu\) này chính là khẩu quyết mà Anh Kha muốn truyền đạt.

Xâu \(cu\) được gọi là xuất hiện trong xâu \(S\) nếu sau khi xoá đi một vài hoặc không kí tự trong xâu \(S\) và ghép các kí tự còn lại theo đúng thứ tự tương đối của nó, ta thu được xâu \(cu\).

Ví dụ, xâu \(cu\) xuất hiện trong xâu \(cạcu\) nhưng không xuất hiện trong xâu \(amivippro\)

Input

• Dòng đầu tiên chứa \(N\) là độ dài xâu \(S\).

• Dòng thứ hai chứa \(N\) kí tự thuộc xâu \(S\).

Output

• Hãy in ra số lần xuất hiện nhiều nhất có thể của xâu \(cu\) sau khi thêm một kí tự bất kì vào xâu \(S\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 1000\).

• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 5000\)

• Subtask \(3\) (\(40\%\) số điểm): \(n \leq 10^6\)

Example

8
 cuomgavl

2

6
cumcal

3

Sau khi truyền thụ bí thuật cho huynh đệ cuom1999, Anh Kha kết thúc kì nghỉ Tết và trở lại công việc của mình là BoiToanDao. Thầy bói Anh Kha nổi tiếng trong cộng đồng chuyên Tin với công thức tính chỉ số tình bạn đặc biệt. Một ngày nọ, Bảo Anh tìm tới tận nhà Anh Kha để xin một quẻ về tình bạn của mình với bạn nữ cùng tên. Không may cho Bảo Anh là Anh Kha lại vắng nhà, nhưng lại may cho cậu là cậu đã tìm được công thức trứ danh. Để tính chỉ số tình bạn giữa 2 bạn khác giới, Anh Kha làm như sau:

• Đầu tiên ghép tên 2 bạn để tạo thành một cái tên dài. Ví dụ bạn nam là Doan Nguyen Thanh Luong, bạn nữ là Huynh Phan Nhat Vy thì Anh Kha sẽ ghép lại tạo thành chuỗi Doan Nguyen Thanh Luong Huynh Phan Nhat Vy
• Sau đó Anh Kha mã hóa chuỗi dài trên bằng cách thay mỗi từ trong đó bằng một số là số kí tự trong chuỗi. Lưu ý rằng, công thức này chỉ có hiệu quả nếu các từ có độ dài không quá \(10\). Nếu từ nào có độ dài \(10\) thì Anh Kha mã hóa thành \(0\). Ví dụ, Doan Nguyen Thanh Luong Huynh Phan Nhat Vy được mã hóa thành \([4,6,5,5,5,4,4,2]\)
• Anh Kha thực hiện thao tác sau liên tục cho đến khi dãy còn lại chỉ có 2 số: Giả sử đang có dãy \(a\). Anh Kha muốn tạo một dãy \(b\) mới với quy tắc: lần lượt chọn 2 số \(a_i,a_{i+1} (1 \leq i < n)\) rồi thêm tổng của chúng vào dãy \(b\). Nếu tổng của chúng \(\geq 10\) thì chỉ giữ lại chữ số hàng đơn vị. Sau đó lại áp dụng thao tác với dãy \(b\)... Hai chữ số cuối cùng sẽ là chỉ số tình bạn giữa hai người (không có gì là tuyệt đối cả :)) ).

Ví dụ: \([4,6,5,5,5,4,4,2] \rightarrow [0,1,0,0,9,8,6] \rightarrow [1,1,0,9,7,4] \rightarrow [2,1,9,6,1] \rightarrow [3,0,5,7] \rightarrow [3,5,2] \rightarrow [8,7]\)

Vì lo sợ mình và bạn nữ cùng tên đang trong mối quan hệ trên tình bạn, dưới tình iu nên Bảo Anh không tài nào tập trung tính toán được. Bạn hãy giúp Bảo Anh tính ra chỉ số tình bạn của cậu ấy nhé.

Input

• Dòng đầu tiên gồm 2 số nguyên \(n,m\)
• Dòng thứ 2 gồm \(n\) chuỗi kí tự thể hiện tên của bạn nam
• Dòng thứ 3 gồm \(m\) chuỗi kí tự thể hiện tên của bạn nữ

Output

• In ra chỉ số tình bạn của Bảo Anh và bạn nữ cùng tên

Constraints

• \(1 \leq n,m \leq 10^5\)
• \(1 \leq\) độ dài mỗi chuỗi \(\leq 10\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 1000\)
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10000\)
• Subtask \(3\) (\(34\%\) số điểm): \(n \leq 100000\)

Example

4 4 
Doan Nguyen Thanh Luong
Huynh Phan Nhat Vy

87

1 3
anhkha2003
Nguyen Ngoc Anh

67

Hiếu rất thích làm bài trên Codeforces. Một lần, trong contest Hiếu gặp bài toán như sau: "Cho một dãy số có \(n\) \((n \leq 1000)\) số \(a_1,a_2,\dots,a_n\). Tìm hai chỉ số \(i<j\) sao cho \(a_i+a_j\) lớn nhất. Bạn phải giải bài toán cho \(t\) \((t\leq 10^3)\) trường hợp khác nhau. Biết rằng tổng các số n trong một input không vượt quá \(1000\)". "Quá đơn giản", Hiếu thốt lên và bắt tay ngay vào code thuật toán \(O(n^2)\) đỉnh cao mà anh chỉ tốn \(1000ms\) để nghĩ ra. Ơ mà khoan, mỗi trường hợp là \(n^2\), có \(t\) test, vậy tổng cộng là \(n^2∗t=10^9\) phép tính cơ mà. "TLE mất rồi", Hiếu suy sụp. Hiếu sau đó nghĩ ra được thuật \(O(n)\) và AC dễ dàng. Tuy nhiên, sau khi thử submit lại code \(O(n^2)\), anh lại nhận được dòng chữ AC trong sự ngỡ ngàng. Vì sao vậy? Để đơn giản bài toán, Hiếu đã viết lại đề như sau (các bạn không cần đọc phía trên đâu :)):

Cho hai số nguyên \(n, s\) và dãy số nguyên gồm \(n\) số \(a_1, a_2, \dots , a_n\). Hãy tìm dãy số nguyên \(x_1, x_2, \dots , x_n\) thỏa mãn:

• \(x_1 + x_2 + \dots + x_n \leq s\)
• \(x_i \geq a_i, i=1,2,\dots ,n\)
• \(A = x_1^2 + x_2^2 + \dots + x_n^2\) đạt giá trị lớn nhất

Bạn cần phải tìm giá trị lớn nhất của \(A\). Ngoài ra, bạn phải xử lý \(q\) truy vấn, mỗi truy vấn gồm hai số \(i,x\) và bạn cần update \(a_i=x\). Hãy in ra giá trị lớn nhất của \(A\) sau mỗi lần truy vấn.

Input

• Dòng đầu tiên bao gồm 2 số nguyên \(n, s\).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots , a_n\).
• Dòng thứ ba chứa 1 số nguyên \(q\).
• \(q\) dòng tiếp theo, mỗi dòng gồm 2 số nguyên \(i,x\) biểu diễn truy vấn cập nhật \(a_i=x\).

Output

• Hãy in ra \(q+1\) dòng. Dòng đầu chứa kết quả khi chưa thực hiện truy vấn nào, và \(q\) dòng sau chứa kết quả sau khi thực hiện mỗi truy vấn.

Constraints

• \(n \leq 10^5\)
• \(s \leq 10^9\)
• \(0 \leq a_i \leq 10^4\)
• \(q \leq 10^5\)
• \(1 \leq i \leq n\)
• \(0 \leq x \leq s\)
• Dữ liệu đảm bảo \(\sum_{i=1}^{n}a_i \leq s\) tại mọi thời điểm.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(q=0, a_i=0, \forall i=1,2,\dots, n\)
• Subtask \(2\) (\(20\%\) số điểm): \(q=0, a_1=a_2=\dots=a_n\)
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^3, q=0\)
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 10^5, q=0\)
• Subtask \(5\) (\(20\%\) số điểm): \(n \leq 10^5, q \leq 10^5\)

Example

3 4
1 1 1
0

6

3 5
1 1 1
3
1 2
2 2
1 1

11
11
9
11