Có ~n~ chiếc kẹo và ~m~ em bé. Kiểm tra xem có thể chia đều số kẹo đó cho mỗi em được hay không.

Input

Gồm hai dòng, dòng đầu tiên chứa số nguyên dương ~n~ và dòng thứ hai chứa số nguyên dương ~m~. (~m, n \leq 2 \times 10^9~)

Output

In ra YES nếu như có thể chia đều ~n~ chiếc kẹo đó cho ~m~ em, nếu không in ra NO.

Sample Tests

Cho số nguyên dương ~n~, đếm số cách để chia ~n~ chiếc kẹo thành các phần bằng nhau (mà không phá vỡ hay làm hỏng chiếc kẹo nào).

Input

Gồm một số nguyên dương ~n~ duy nhất. (~n \leq 1000~)

Output

In ra số cách chia ~n~ chiếc kẹo thành các phần bằng nhau.

Sample Test

Input:

10

Output:

4

Giải thích:

Các cách chia thoả mãn là:

• Chia thành ~1~ phần, mỗi phần ~10~ chiếc kẹo.
• Chia thành ~2~ phần, mỗi phần ~5~ chiếc kẹo.
• Chia thành ~5~ phần, mỗi phần ~2~ chiếc kẹo.
• Chia thành ~10~ phần, mỗi phần ~1~ chiếc kẹo.

Nhập 1 số nguyên dương ~N~, sau đó nhập tiếp 1 dãy gồm ~N~ số nguyên. Kiểm tra xem dãy vừa nhập có đối xứng hay không. Có thì ghi YES, ngược lại ghi NO.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~).
• Dòng tiếp theo chứa ~N~ số nguyên ~x~ (~|x| \leq 10^9~).

Output

Nếu dãy đối xứng thì in ra YES, ngược lại in ra NO.

Sample Test

Input:

5
1 6 2 6 1

Output:

YES

Cho số nguyên dương ~N~. Đếm xem trong các chữ số của ~N~ có bao nhiêu số nguyên tố.

Input

• Gồm một số nguyên dương ~N~ duy nhất.
  
  

Output

• In ra số lượng chữ số là số nguyên tố trong ~N~.
  
  

Subtasks

• Subtask 1 (~50\%~ số điểm): ~N \leq 10^4~.
• Subtask 2 (~20\%~ số điểm): ~N \leq 10^8~.
• Subtask 3 (~30\%~ số điểm): ~N \leq 10^{100}~.
  
  

Sample Test

Input

23452345

Output

6

Note

• Có ~6~ chữ số nguyên tố trong ~N~ là ~2, 3, 5, 2, 3, 5~.

Cho một số nguyên dương ~n~. Hãy liệt kê tất cả số nguyên tố nhỏ hơn hoặc bằng ~n~.

Input

Gồm một số nguyên dương ~n~ duy nhất (~2 \leq n \leq 10^5~).

Output

In ra tất cả các số nguyên tố không vượt quá ~n~ theo thứ tự tăng dần trên cùng một dòng.

Sample Test

Input:

14

Output:

2 3 5 7 11 13

Con phố ~X~ có ~n~ cái cột đèn được đánh số từ ~1~ đến ~n~. Tuy nhiên, trận bão tàn khốc vừa qua đã khiến ~t~ trong ~n~ cây đèn này bị đổ. Sắp tới, thành phố cần tổ chức một lễ hội lớn tại đây, và yêu cầu cần tổ chức tại vị trí có ít nhất ~k~ cái đèn còn nguyên vẹn liên tiếp. Vì thời gian gấp rút, bạn được thành phố yêu cầu tìm xem cần phải sửa chữa ít nhất bao nhiêu cây đèn để có thể tổ chức lễ hội.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n, k, t~ ~(1 \le t, k \le n \le 10^5)~.
• ~t~ dòng tiếp theo, mỗi dòng gồm một số nguyên dương là vị trí có cây đèn bị đổ.
  
  

Output

• In ra một số nguyên duy nhất là số cây đèn cần được sửa chữa.
  
  

Sample Test

Input:

10 6 5
2
10
1
5
9

Output:

1

Note: Sửa cây đèn tại vị trí ~5~ và chọn các cây ~3, 4, 5, 6, 7~ để tổ chức lễ hội.

Điều kiện thoả mãn dãy ngoặc đúng gồm 2 loại ngoặc ( ) và [ ] được định nghĩa như sau:

• Dãy rỗng "" là một dãy ngoặc đúng.
• Nếu dãy ~A~ là một dãy ngoặc đúng thì ~(A)~ và ~[A]~ là các dãy ngoặc đúng.
• Nếu dãy ~A~ và dãy ~B~ là hai dãy ngoặc đúng thì ~A + B~ là một dãy ngoặc đúng.

Cho xâu ~s~ là một dãy ngoặc gồm ~2~ loại ngoặc như trên (~4~ loại kí tự). Nếu xâu ~s~ là một dãy ngoặc đúng, với mỗi kí tự của ~s~, in ra số thứ tự của ngoặc tương ứng với nó. Nếu không, in ra ~-1~. Các kí tự được đánh số từ ~1~.

Input

• Gồm một dòng chứa xâu ngoặc ~s~ ~(1 \le |s| \le 2 \times 10^5)~.
  
  
  

Output

• Nếu ~s~ là dãy ngoặc đúng, in ra ~1~ dòng gồm ~|s|~ số nguyên dương, số thứ ~i~ là số thứ tự của ngoặc tương ứng với ngoặc thứ ~i~.
• Nếu không, in ra ~-1~.
  
  

Sample Test 1

Input:

([])[]

Output:

4 3 2 1 6 5

Note:

• Số thứ tự của các cặp ngoặc là ~1-4, 2-3~ và ~5-6~.
  
  

Sample Test 2

Input:

([)]

Output:

-1

Note:

• Xâu ~s~ không phải là dãy ngoặc đúng.

Cho ~1~ dãy số có ~N~ phần tử nguyên ~a_1, a_2, \dots, a_n~ đă được sắp xếp theo thứ tự không giảm.

Hãy trả lời ~T~ truy vấn: In ra giá trị của số lớn nhất mà bé hơn số ~X~ được nhập vào. Nếu không có giá trị thỏa mãn thì in ra ~-1~.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~. (~N \leq 10^6~)
• Dòng thứ hai chứa ~N~ phần tử nguyên ~a_1, a_2, \dots, a_n~. (~|a_i| \leq 10^9~)
• Dòng thứ ba chứa số nguyên dương ~T~. (~T \leq 10^5~)
• Dòng thú tư chứa ~T~ số nguyên ~X~ tương ứng với ~T~ truy vấn. (~|X| \leq 10^9~)

Output

• In ra câu trả lời của các truy vấn trên một dòng, cách nhau bởi dấu cách.

Subtasks

• Subtask ~1~ (~50\%~ số điểm): ~N \leq 10^3~.
• Subtask ~2~ (~50\%~ số điểm): Không có thay đổi gì thêm.

Sample Test

Input:

8
1 1 1 3 3 3 5 5
5
2 5 6 0 1

Output:

1 3 5 -1 -1

Cho một dãy ~a~ gồm ~n~ phần tử. Ban đầu tất cả phần tử đều có giá trị bằng ~0~. Có ~m~ thao tác, thao tác thứ ~i~ gồm ba số nguyên ~L,R,X~ có nghĩa là tăng các phần tử từ vị trí thứ ~L~ tới vị trí thứ ~R~ lên ~X~ đơn vị.

Hãy tìm cách bỏ đi một thao tác để sau khi thực hiện hết ~M-1~ thao tác còn lại thì giá trị lớn nhất của dãy số là nhỏ nhất.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương ~n,m~.
• ~m~ dòng sau, mỗi dòng gồm ba số nguyên dương ~L,R,X~.
  
  

Output

• In ra giá trị lớn nhất của dãy số sau khi bỏ đúng một thao tác thỏa mãn yêu cầu đề bài.
  
  

Constraints

• ~1 \le n,m \le 10^5~.
• ~|x| \le 10^9~.
  
  

Subtasks

• ~25\%~ số test: ~N \le 10^2, M \le 10^2~.
• ~25\%~ số test: ~N \le 10^5, M \le 10^2~.
• ~25\%~ số test: ~N \le 10^2, M \le 10^5~.
• ~25\%~ số test: ~N \le 10^5, M \le 10^5~.
  
  

Sample Test 1

Input:

5 2
1 3 3
2 5 2

Output:

2

Sample Test 2

Input:

5 3
1 3 3
2 5 2 
5 5 8

Output:

5

Vùng đất Midland đang có chiến tranh tàn khốc. Bạn đang ở vùng giao tranh, và giờ phải gửi tài liệu mật từ đơn vì tới cho sở chỉ huy. Vùng này được biểu diễn dưới dạng một ma trận ~n \times m~, ô ở hàng ~i~ cột ~j~ được gọi là ô ~(i,j)~.

Công việc này chưa bao giờ là dễ dàng. Một vài ô đã bị địch cài bom và không biết khi nào sẽ phát nổ. Bạn chỉ biết rằng loại bom này có sức công phá là ~r~, có nghĩa là nếu bom ở ô ~(i,j)~, khi nó phát nổ thì các ô ~(u,v)~ thỏa mãn ~|i-u| + |j-v| \le r~ sẽ bị tàn phá (ô ~(i,j)~ và ~(u,v)~ đều nằm trong bảng). Những ô ~(u,v)~ như vậy gọi là những ô bị ảnh hưởng bởi bom.

Đây là tài liệu mật, tất nhiên chỉ huy của bạn không muốn nhận một sự rủi ro nào, vậy nên bạn được lệnh phải tìm một đường đi ngắn nhất từ đơn vị tới sở chỉ huy sao cho không được đi qua ô nào bị ảnh hưởng bởi bom. Biết rằng bạn có thể đi sang ~4~ ô kề cạnh với ô đang đứng và mỗi ô ~(i,j)~ sẽ được miêu tả bằng một kí tự như sau:

• ~c(i,j) =~ ., nếu đây là một ô bình thường có thể đi.
• ~c(i,j) =~ *, đây là vùng nguy hiểm tuyệt đối không được đi vào.
• ~c(i,j) =~ +, đây là ô có bom, như đã nói, các ô nằm cách ô này khoảng cách không quá ~r~ (kể cả chính nó) sẽ không thể đi vào.
• ~c(i,j) =~ S, đây là đơn vị của bạn, sẽ chỉ có duy nhất một ô thế này xuất hiện.
• ~c(i,j) =~ T, đây là sở chỉ huy, sẽ chỉ có duy nhất một ô thế này xuất hiện.
  
  

Input

• Dòng đầu tiên gồm ~3~ số nguyên ~n,m,r~, miêu tả kích thước bảng và vùng ảnh hưởng của bom.
• ~n~ dòng sau, mỗi dòng gồm ~m~ kí tự miêu tả vùng đất.
• Dữ liệu luôn đảm bảo ô chứa kí tự ~S~ và ~T~ không bị ảnh hưởng bởi ô chứa bom nào.
  
  

Output

• In ra một dòng là đường đi ngắn nhất từ đơn vị tới sở chỉ huy sao cho không được đi qua ô nào bị ảnh hưởng bởi bom. Nếu không có một đường đi nào như vậy, in ra ~-1~.
  
  

Constraints

• ~1 \le n,m \le 1000~
• ~0 \le r \le 1000~
  
  

Subtasks

• ~20\%~ số điểm: Không có ô nào có ~c(i,j) = *~ hoặc ~c(i,j) = +~.
• ~20\%~ số điểm: ~r = 0~.
• ~30\%~ số điểm: ~n,m \le 100~.
• ~30\%~ số điểm: Không có ràng buộc gì thêm.
  
  

Sample Test 1

Input:

3 4 1
S...
....
...T

Output:

5

Sample Test 2

Input:

3 4 0
S.+T
*.*.
*...

Output:

7

Sample Test 3

Input:

4 4 1
S..*
*...
+.*.
.T..

Output:

8

Hè đã tới, ~mrtee~ muốn cho các học sinh của mình vận động một chút. Thầy đã lập ra một cuộc thi nhảy xa, tuy nhiên điều luật của nó thì rất lạ.

Nếu chiếu trên trục ~OX~, đường nhảy sẽ bắt đầu từ điểm ~1~ và kết thúc tại điểm ~n~. Bạn sẽ xuất phát từ điểm ~0~ và được nhảy bao nhiêu lượt tùy thích, miễn là không ra khỏi phạm vi ~[1,n]~. Tuy nhiên, mỗi lượt bạn phải nhảy một quãng đường nguyên dương và ở lần nhảy thứ ~i~, bạn phải nhảy một quãng đường có độ chia hết cho ~k+i-1~. Tất nhiên, bạn sẽ được cung cấp trước ~2~ giá trị ~n~ và ~k~.

Là một ~coder~ yêu thích toán học, bạn không quan tâm tới việc thắng thua trong cuộc thi này lắm, mà chỉ hứng thú với việc đếm xem với mỗi vị trí ~i~ thuộc đoạn ~[1,n]~, có bao nhiêu cách nhảy khác nhau từ điểm xuất phát tới đó.

Hãy thử lập trình và giải đáp câu hỏi ấy!

Input

• Gồm một dòng chứa hai số nguyên dương ~n, k~.
  
  

Output

• In ra ~n~ số nguyên, số thứ ~i~ là số cách để nhảy từ điểm ~0~ tới điểm ~i~, vì kết quả có thể rất lớn nên hãy lấy phần dư với modulo ~10^9+7~.
  
  

Constraints

• ~1 \le k \le n \le 2*10^5~
  
  

Subtasks

• ~35\%~ số điểm: ~n \le 300~.
• ~40\%~ số điểm: ~n \le 4000~.
• ~25\%~ số điểm: ~n \le 2*10^5~.
  
  

Sample Test 1

Input:

12 1

Output:

1 1 2 2 3 4 5 6 8 10 12 15

Sample Test 2

Input:

15 3

Output:

0 0 1 0 0 1 1 0 1 1 1 2 1 1 3

Giải thích

• Ở ví dụ ~1~, các cách để đến điểm ~6~ là ~[0,6],[0,4,6],[0,2,6],[0,1,3,6]~.
• Ở ví dụ ~2~, các cách để đến điểm ~15~ là ~[0,15],[0,3,12],[0,6,10,15]~

Cho một cây có ~n~ đỉnh đánh số từ ~1~ đến ~n~ và đỉnh ~1~ là gốc. Mỗi đỉnh trên đều được tô màu, đỉnh thứ ~i~ được tô bởi màu ~a_i~.

Một tập hợp các đỉnh trên được gọi là đẹp nếu có hơn một nửa số đỉnh trong tập được tô bởi cùng một màu.

Có ~q~ truy vấn, mỗi truy vấn thuộc một trong các dạng sau:

• Truy vấn dạng: ~1~ ~u~, truy vấn này kiểm tra xem tập đỉnh gồm các đỉnh nằm trong cây con gốc ~u~ có phải là một tập đẹp hay không;
• Truy vấn dạng: ~2~ ~u~, truy vấn này kiểm tra xem tập đỉnh gồm các đỉnh nằm ngoài cây con gốc ~u~ có phải là một tập đẹp hay không;
• Truy vấn dạng: ~3~ ~u~ ~v~, truy vấn này kiểm tra xem tập đỉnh gồm các đỉnh nằm trên đường đi đơn từ ~u~ tới ~v~ (tính cả ~u~ và ~v~) có phải là một tập đẹp hay không.
  
  

Input

• Dòng đầu tiên chứa số nguyên dương ~n, q~ là số đỉnh của cây và số lượng truy vấn.
• Dòng thứ hai chứa ~n~ số, số thứ ~i~ là ~a_i~ mô tả màu sắc của đỉnh ~i~. ~(1 \le a_i \le n)~
• ~n - 1~ dòng tiếp theo, mối dòng chứa hai số nguyên dương ~u, v~ ~(1 \le u, v \le n)~ mô tả cạnh nối hai đỉnh ~u~ và ~v~.
• Tiếp theo gồm có ~q~ dòng mô tả các truy vấn. Các truy vấn thuộc ~1~ trong ~3~ dạng ~1~ ~u~, ~2~ ~u~ hoặc ~3~ ~u~ ~v~.
  
  

Output

• Với mỗi truy vấn, in ra kết quả lần lượt trên các dòng khác nhau.
  
  

Constraints

• ~1 \le n,q \le 50000~
  
  

Subtasks

• Subtask ~1~ ~(20\%)~: ~1 ≤ n, q ≤ 2 000~.
• Subtask ~2~ ~(20\%)~: ~1 ≤ n, q ≤ 50 000~ và mỗi đỉnh có tối đa ~2~ cạnh nối trực tiếp.
• Subtask ~3~ ~(20\%)~: ~1 ≤ n, q ≤ 50 000~ và ~1 ≤ ai ≤ 2~
• Subtask ~4~ ~(20\%)~: ~1 ≤ n, q ≤ 50 000~ và không có truy vấn loại ~3~.
• Subtask ~5~ ~(20\%)~: không có ràng buộc nào thêm.
  
  

Sample Test

Input:

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

Output:

1
-1
-1
3
2

Giải thích:

Dưới đây là hình vẽ của ví dụ thứ nhất với màu ~1~ được tô màu xám, màu ~2~ được tô màu đỏ và màu ~3~ được tô màu xanh.

• Truy vấn ~1~: xét các đỉnh trong cây con gốc ~2~ là ~{2, 4, 5, 6, 8}~, màu ~1~ xuất hiện ~3~ lần.
• Truy vấn ~2~: xét các đỉnh trên đường đi từ ~4~ đến ~6~ là ~{2, 4, 5, 6}~, không có màu nào xuất hiện quá ~2~ lần.
• Truy vấn ~3~: xét các đỉnh nằm ngoài cây con gốc ~6~ là ~{11, 2, 3, 4, 5, 7}~, không có màu nào xuất hiện quá ~13~ lần.
• Truy vấn ~4~: xét các đỉnh nằm ngoài cây con gốc ~5~ là ~{1, 2, 3, 4, 7}~, màu ~3~ xuất hiện ~3~ lần.
• Truy vấn ~5~: xét các đỉnh nằm trên đường đi từ ~1~ đến ~5~ là ~{1, 2, 5}~, màu ~2~ xuất hiện ~2~ lần.

Chán ngán với các trận chiến cũng như nắm bắt được cơ hội kinh doanh, Satoshi cùng chú pokemon của anh ấy - Pikachu đã lập ra một cửa hàng dịch vụ sạc xe điện.

Một ngày nọ, cửa hàng nhận được ~n~ yêu cầu sạc xe, chiếc xe thứ ~i~ cần ~a_i~ phút để sạc đầy bình. Để công việc diễn ra nhanh chóng, Satoshi sẽ chia ~n~ xe ra thành các nhóm tương ứng với các đoạn con liên tiếp theo số lượng tùy ý. Sau đó, anh ấy sẽ để Pikachu sạc điện cho lần lượt từng nhóm xe. Giả sử nhóm thứ ~i~ gồm các xe có chỉ số trong đoạn ~[l_i,r_i]~, tất cả các xe trong nhóm ~i~ sẽ mất ~charge(i) = max_{j \in [l_i,r_i]}(a_j)~ phút để được sạc.

Gọi ~group(i)~ là nhóm của người thứ ~i~. Thời gian chờ của người thứ ~i~, còn được gọi là ~wait(i)~ được tính bằng tổng thời gian sạc của các nhóm xe trước đó (các nhóm xe có chỉ số bé hơn ~group(i)~) cộng với thời gian sạc của nhóm xe ~group(i)~. Nói cách khác, ~wait(i) = \sum_{j=1}^{group(i)} charge(j)~.

Hãy giúp Satoshi tìm được cách phân chia nhóm tối ưu nhất sao cho tổng thời gian chờ đợi của toàn bộ các khách hàng là nhỏ nhất. Nói cách khác, hãy tối ưu cách chia nhóm sao cho ~\sum_i^n wait(i)~ là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~.
  
  

Output

• In ra tổng thời gian chờ đợi nhỏ nhất.
  
  

Constraints

• ~1 \le N \le 10^6~.
• ~1 \le a_i \le 10^9~.
  
  

Subtasks

• Subtask ~1~ ~(20\%)~: ~1 \le n \le 1500~ và ~a_i~ không giảm.
• Subtask ~2~ ~(20\%)~: ~a_i~ không giảm.
• Subtask ~3~ ~(20\%)~: ~a_i~ không tăng.
• Subtask ~4~ ~(20\%)~: ~1 \le n \le 1500~.
• Subtask ~5~ ~(20\%)~: Không có ràng buộc gì thêm.
  
  

Sample Test

Input:

5
1 3 2 6 1

Output:

27

Giải thích: Chia thành hai nhóm ~(1,3,2)~ và ~(6,1)~. Nhóm một mất ~3~ phút để sạc và nhóm ~2~ mất ~6~ phút. Vậy các xe ở nhóm ~1~ phải chờ ~3~ phút và các xe ở nhóm hai phải chờ ~9~ phút.

Đáp án là ~3 + 3 + 3 + 9 + 9 = 27~.