Thành phố Hạ Long có ~N~ nút giao thông, được đánh số từ ~1~ đến ~N~. Giữa một số cặp nút giao thông có các con đường hai chiều nối trực tiếp, và việc đi qua mỗi con đường mất đúng ~1~ phút.

Vào một ngày đẹp trời, thầy Hưng quyết định dẫn hai cậu học trò Kiên và Khánh đi dạo khắp thành phố. Xuất phát từ nút giao thông ~S~, cả ba người muốn có một chuyến hành trình kéo dài đúng ~K~ phút, và kết thúc tại nút giao thông ~T~.

Điều đặc biệt là trong quá trình di chuyển, thầy Hưng có thể đi qua bất kỳ nút giao thông nào nhiều lần (kể cả ~S~ và ~T~).

Nhiệm vụ của bạn là đếm xem có bao nhiêu tuyến đường hợp lệ mà thầy Hưng có thể chọn. Vì kết quả có thể rất lớn, hãy in ra phần dư của số đó chia cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa bốn số nguyên dương ~N, S, T, K~ ~(S, T \leq N \le 50; K \le 10^{18})~.
• Tiếp theo là ~N~ dòng, mỗi dòng chứa ~N~ số nguyên ~c_{i,j}~. Trong đó:
  • ~c_{i,j} = 0~ nếu không có đường;
  • ~c_{i,j} = 1~ nếu tồn tại con đường hai chiều nối trực tiếp giữa nút ~i~ và nút ~j~.

Output

• Một số nguyên duy nhất - phần dư của số tuyến đường thỏa mãn chia cho ~10^9 + 7~.

Sample Input

3 1 1 4
0 1 0
1 0 1
0 1 0

Sample Output

2

Trang trại của nông dân John vừa mới bước vào mùa vụ bận rộn nhất trong năm. Sáng sớm, khi đồng hồ vừa điểm ~0~, John đã phải bắt đầu ngày làm việc kéo dài đến tận thời điểm ~10^9~. Cả khoảng thời gian đó được chia thành từng đơn vị nhỏ - và trong mỗi đơn vị thời gian, John chỉ có thể tập trung làm đúng một công việc duy nhất, từ đầu đến cuối.

Tuy nhiên, do số lượng công việc được gửi đến quá nhiều, John biết rằng anh sẽ không thể hoàn thành hết tất cả. Mỗi công việc kèm theo thông tin về:

• Hạn chót ~S_k~ - John chỉ có thể hoàn thành công việc này nếu bắt đầu và kết thúc nó trước hoặc đúng thời điểm ~S_k~.
• Khoản tiền công ~P_k~ - số tiền John nhận được nếu hoàn thành công việc đúng hạn.

Mỗi công việc mất đúng ~1~ đơn vị thời gian để hoàn thành. John hoàn toàn có thể bỏ qua một số công việc để tối đa hóa tổng lợi nhuận của mình.

Nhiệm vụ của bạn là: hãy giúp John lên kế hoạch lựa chọn các công việc sao cho tổng số tiền anh thu về là lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N \leq 10^5)~ - số lượng công việc được gửi đến.
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~S_k~ và ~P_k~ ~(S_k, P_k \leq 10^9)~, lần lượt là hạn chót và lợi nhuận của công việc thứ ~k~.

Output

• In ra một số nguyên duy nhất - tổng lợi nhuận lớn nhất mà John có thể đạt được.

Sample Input

3
2 10
1 5
1 7

Sample Output

17

Notes

• John không thể làm cả 3 công việc vì thời gian hạn hẹp. Chiến lược tối ưu là:
  • Thực hiện công việc số 3 (hạn chót 1, lợi nhuận 7).
  • Sau đó thực hiện công việc số 1 (hạn chót 2, lợi nhuận 10).
  • Tổng lợi nhuận thu được: (7 + 10 = 17).

Trên một hòn đảo nhỏ giữa biển lớn, có một trạm nghiên cứu đặt ba cột ăng-ten ở những vị trí khác nhau trong không gian ba chiều để theo dõi sóng từ các vệ tinh. Mỗi cột được gắn một cảm biến, và nhà khoa học muốn biết độ ngắn nhất của đoạn tín hiệu truyền từ một cảm biến ~A~ tới đường thẳng đi qua hai cột ~B~ và ~C~ - tức là khoảng cách trực giao từ điểm đến đường thẳng trong không gian.

Bạn được giao nhiệm vụ giúp nhà khoa học xử lý nhiều phép đo: cho từng Bộ Dữ Liệu gồm tọa độ của ba điểm ~(A, B, C)~ trong không gian ~3D~, hãy tính khoảng cách ngắn nhất từ điểm ~A~ đến đường thẳng ~BC~. Kết quả phải được in theo từng dòng, làm tròn chính xác đến hai chữ số thập phân.

Input

• Dòng đầu chứa một số nguyên dương ~T~ ~(T \le 10^4)~ - số bộ dữ liệu (số phép đo).

• Mỗi bộ dữ liệu gồm ~9~ số nguyên trên một dòng, theo thứ tự:

  • ~x_A; y_A; z_A; ; x_B; y_B; z_B; ; x_C; y_C; z_C~
  • ~(x_A,y_A,z_A)~ là tọa độ điểm ~A~;
  • ~(x_B,y_B,z_B)~ là tọa độ điểm ~B~;
  • ~(x_C,y_C,z_C)~ là tọa độ điểm ~C~.

• Lưu ý:

  • Các tọa độ đều có trị tuyệt đối không vượt quá ~10^{9}~.
  • Dữ liệu đảm bảo ~B~ khác ~C~ (tức đường thẳng ~BC~ xác định duy nhất).

Output

• In ra ~T~ dòng, mỗi dòng chứa một số thực: khoảng cách từ điểm ~A~ tới đường thẳng ~BC~ tương ứng với bộ dữ liệu đó, làm tròn đến hai chữ số thập phân.

Sample Input

2
2 3 0 1 -1 0 10 100 0
3 0 -1 -5 5 2 1 1 3

Sample Output

0.64
4.28

Trong một vùng đất xa xôi, có một ngôi làng kỳ lạ nơi mà mọi con số đều được nhân cách hóa. Các con số sống hòa bình với nhau, nhưng trong truyền thuyết làng có nhắc đến một Cặp đôi định mệnh: đó là hai con số mà khi kết hợp lại theo một quy tắc bí ẩn, chúng tạo nên một giá trị đặc biệt ~K~.

Cụ thể, có một dãy gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~. Những cư dân của ngôi làng tin rằng một cặp chỉ số ~(i, j)~ ~(~ với ~1 \leq i \leq j \leq N)~ sẽ được gọi là cặp đôi định mệnh nếu thỏa mãn điều kiện sau: ~a_i + a_j^2 = K~ với (K) là một số nguyên dương đã được định sẵn từ đầu.

Nhiệm vụ của bạn: là tìm ra xem trong ngôi làng có bao nhiêu cặp đôi định mệnh như thế tồn tại.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ ~(N \leq 10^5; K \leq 10^9)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ ~(1 \leq a_i \leq 500)~.

Output

• In ra một số nguyên duy nhất: số lượng cặp ~(i, j)~ thỏa mãn điều kiện đã cho.

Sample Input

3 5
1 2 1

Sample Output

1

Người ta vẫn thường kể rằng quãng thời gian học quân sự thời sinh viên là một trong những kỷ niệm đẹp nhất, vui vẻ nhất của tuổi trẻ. Có người bảo rằng: đi học quân sự mà chưa từng ngủ gật trong lớp, chưa từng thức trắng đêm cùng bạn bè hay chưa từng tìm thấy một mối tình đầu thì chưa trọn vẹn.

Himt – một chàng trai tuổi mười tám, tràn đầy sức trẻ – đã đi qua nửa quãng thời gian quân sự trong sự trống vắng. Thế rồi anh gặp Hiền, cô gái khiến anh mỗi ngày đều mong ngóng đến giờ tan học để kịp về sớm một giây mà đi chơi cùng.

Nhưng Hiền không dễ dàng nhận lời đồng hành. Cô gái thích những thử thách, thích đặt ra những câu đố hóc búa. Và rồi, Hiền nói: "Anh hãy đếm giúp em xem có bao nhiêu tổng khác nhau có thể tạo thành từ một dãy gồm ~N~ số nguyên, trong đó số nhỏ nhất là ~A~ và số lớn nhất là ~B~. Nếu làm được, em sẽ đi chơi cùng anh."

Himt loay hoay cả ngày mà không tìm ra đáp án. Giờ đây, anh nhờ bạn - một coder đáng tin cậy - hãy giúp anh giải bài toán này để chinh phục Hiền.

Input

• Gồm một dòng duy nhất chứa ~3~ số nguyên ~N, A, B~ ~(1 \leq N, A, B \leq 10^9)~.

Output

• Gồm một dòng duy nhất là số lượng tổng khác nhau.

Sample Input

4 4 6

Sample Output

5

Notes

• Có 5 tổng khác nhau:
  • (18 = 4 + 4 + 4 + 6)
  • (19 = 4 + 4 + 5 + 6)
  • (20 = 4 + 5 + 5 + 6)
  • (21 = 4 + 5 + 6 + 6)
  • (22 = 4 + 6 + 6 + 6)

Một buổi sáng đẹp trời, Bờm ra vườn thu hoạch được một giỏ to đầy ắp táo - đúng ~n~ quả. Bờm là người hào phóng: trên đường về, cậu gặp rất nhiều bạn bè và mỗi khi gặp một người bạn, Bờm đều muốn chia cho bạn mình một nửa của cái gì đó. Nhưng Bờm lại hơi kỳ quặc và vụng về trong cách chia:

• Với một số bạn, Bờm chỉ cho một nửa quả táo (tức là nửa quả, có thể xuất hiện nếu lúc đó giỏ không có số nguyên quả).
• Với một số bạn khác, Bờm cho một nửa số quả táo hiện có trong giỏ (tức là chia số quả đang có làm đôi, và đưa cho bạn nửa đó).
• Do Bờm vụng về, cậu chỉ có thể chia một nửa quả (nửa quả riêng lẻ) hoặc chia nửa phần của tổng số quả; nói cách khác, kết quả sau mỗi lần cho có thể là số không nguyên (một nửa hoặc số có phần thập phân ~.5~).
• Mỗi lần gặp bạn là một bước hành động: Bờm căn cứ vào "luật chia" của lần đó - cho một nửa quả hay cho nửa số quả hiện có - rồi đưa phần tương ứng cho bạn. Sau khi cho, số quả trong giỏ thay đổi (có thể là số nguyên hoặc số có ~.5~).

Trong ngày hôm ấy, Bờm gặp đúng ~k~ người bạn (lần lượt một người rồi tới người khác). Nhưng Bờm không lập kế hoạch trước: mỗi lần gặp bạn, Bờm có thể chọn kiểu chia là "cho ~0.5~ quả" hoặc "cho một nửa số quả đang có". (Bạn có thể hiểu rằng mỗi lần gặp là một quyết định độc lập: Bờm có thể tùy ý áp dụng một trong hai phép chia, bất kể lần trước đã chọn gì.)

Biết rằng lúc bắt đầu buổi sáng Bờm có đúng ~n~ quả táo, và trong cả ngày Bờm sẽ gặp ~k~ người bạn; hãy xác định tập hợp tất cả các giá trị khác nhau của số quả táo có thể còn lại trong giỏ vào cuối ngày, sau khi Bờm đã thực hiện k lần chia theo các lựa chọn tùy ý như mô tả.

Vì Bờm vụng về chỉ biết chia nửa một quả, tất cả số lượng táo xuất hiện trong quá trình này sẽ là các số có thể biểu diễn dưới dạng ~(x.0)~ hoặc ~(x.5)~ với ~(x)~ là số nguyên không âm.

Input

• Một dòng duy nhất gồm hai số nguyên dương ~n~ và ~k~ ~(1 \le n, k \le 1000)~.

Output

• Dòng đầu tiên: một số nguyên ~m~ — số lượng giá trị khác nhau có thể có của số táo còn lại sau ~k~ lần gặp bạn.
• Dòng thứ hai: ~m~ số thực, sắp xếp theo thứ tự tăng dần, mỗi số in với một chữ số sau dấu phẩy, liệt kê tất cả các giá trị khả dĩ.
• Lưu ý: Các số phải được in dưới dạng thập phân với một chữ số phần thập phân (ví dụ 3.0, 5.5), theo thứ tự tăng dần, và không lặp lại.

Sample Input 1

6 1

Sample Output 1

2
3.0 5.5

Sample Input 2

3 2

Sample Output 2

2
1.0 2.0

Byteasar – một hacker lừng danh với kỹ năng phi thường – đã lọt vào kỳ thi Olympiad Hacking Quốc tế năm nay (IHO). Trong kỳ thi này, một trong những thử thách mà Byteasar phải đối mặt chính là một trò chơi chiến lược căng thẳng với nhà điều hành hệ thống.

Có ~N~ máy tính được đánh số từ ~1~ đến ~N~, mỗi máy tính ~i~ chứa dữ liệu quan trọng có giá trị ~v_i~. Và được nối với nhau thành một mạch vòng. Nghĩa là:

• Máy tính ~i~ được nối trực tiếp với máy tính ~i+1~ ~(i = 1, 2, \dots, N-1)~.
• Máy tính số ~N~ nối trực tiếp với máy tính số ~1~.

Luật chơi:

• Ban đầu, chưa có máy tính nào bị hack hay được bảo vệ.
• Trò chơi diễn ra theo lượt, Byteasar luôn đi trước, sau đó đến lượt nhà điều hành, rồi lại đến Byteasar, và cứ thế luân phiên.
• Trong lượt đầu tiên:
  • Byteasar chọn một máy tính bất kỳ để hack, chiếm được số điểm bằng đúng giá trị dữ liệu trong máy đó.
  • Nhà điều hành chọn một máy tính khác chưa bị hack để bảo vệ. Máy đó bị khóa vĩnh viễn, Byteasar không thể hack.
• Trong các lượt tiếp theo:
  • Byteasar có thể không làm gì, hoặc hack một máy tính chưa bị hack và chưa được bảo vệ, với điều kiện máy tính đó phải nối trực tiếp với một máy tính đã bị hack trước đó.
  • Nhà điều hành có thể không làm gì, hoặc bảo vệ một máy tính chưa bị hack và chưa được bảo vệ, với điều kiện máy tính đó phải nối trực tiếp với một máy tính đã được bảo vệ trước đó.
• Trò chơi kết thúc ngay khi cả hai cùng liên tiếp không thực hiện hành động nào.

Điểm số:

• Mỗi lần Byteasar hack một máy tính ~i~, hắn nhận được ~v_i~ điểm.
• Nhà điều hành thì không ghi điểm, nhiệm vụ của ông chỉ là ngăn Byteasar chiếm được nhiều điểm nhất có thể.
• Byteasar muốn tối đa hóa tổng số điểm, còn nhà điều hành sẽ chơi tối ưu để hạn chế hắn.

Nhiệm vụ: Hãy giúp Byteasar viết chương trình tính số điểm lớn nhất mà hắn có thể đạt được, giả sử cả hai bên đều chơi tối ưu.

Input

• Dòng đầu: số nguyên ~n~ — số máy tính ~(2 \le n \le 500000)~.
• Dòng thứ hai: dãy ~n~ số nguyên ~v_1, v_2, \dots, v_n~ ~(1 \le v_i \le 2000)~

Output

• In ra số điểm lớn nhất Byteasar có thể chiếm được.

Sample Input 1

4
7 6 8 4

Sample Output 1

13

Sample Input 2

5
1 1 1 1 1

Sample Output 2

3

Notes

• Với ví dụ thứ nhất:
  • Byteasar bắt đầu hack máy tính số ~2~, nhận ~6~ điểm.
  • Nhà điều hành ngay lập tức bảo vệ máy tính số ~3~.
  • Byteasar tiếp tục hack máy tính số ~1~, thêm ~7~ điểm.
  • Nhà điều hành bảo vệ máy tính số ~4~.
  • => Tổng cộng Byteasar đạt được ~13~ điểm.

Ở ngôi trường nhỏ của Kevin, mỗi dịp đầu tháng đều có một buổi tiệc đặc biệt dành cho học sinh. Trong buổi tiệc, tất cả lũ trẻ được xếp ngồi quanh một chiếc bàn tròn khổng lồ để cùng nhau ăn uống, trò chuyện và vui chơi.

Có tất cả ~K~ đứa trẻ, được đánh số từ ~1~ đến ~K~. Chúng ngồi thành một vòng tròn kín, và vì ngồi vòng tròn nên:

• Mỗi đứa trẻ sẽ có chính xác ~2~ người bạn ngồi cạnh - một bạn bên trái, một bạn bên phải.
• Không có đứa trẻ nào ngồi "một mình" hoặc có quá nhiều bạn bên cạnh.

Nghe thì tưởng đơn giản, nhưng thật ra việc sắp xếp lại không hề dễ dàng. Lũ trẻ trong trường vốn rất… "khó tính": nhiều đứa đặt ra những mong muốn đặc biệt. Chẳng hạn, có đứa nói rằng: "Tớ muốn ngồi cạnh cậu ~A~!" hoặc: "Tớ chỉ thấy vui nếu có cậu ~B~ ngồi sát bên tớ!".

Mỗi mong muốn như vậy được mô tả bởi một cặp số ~(A, B)~, nghĩa là đứa trẻ ~A~ muốn ngồi cạnh đứa trẻ ~B~. Trong vòng tròn, mong muốn này có thể được thỏa mãn nếu ~A~ ngồi bên trái ~B~, hoặc ~A~ ngồi bên phải ~B~ - miễn sao chúng ở cạnh nhau.

Tuy nhiên, để thỏa mãn tất cả các mong muốn cùng lúc, liệu có cách xếp chỗ nào hợp lý hay không? Đó là câu hỏi khiến các thầy cô đau đầu, và họ cần bạn - một chuyên gia toán - lập trình – giải quyết.

Nhiệm vụ: Với mỗi buổi tiệc, hãy xác định xem có thể sắp xếp tất cả ~K~ đứa trẻ quanh vòng tròn để mọi mong muốn đều được thỏa mãn hay không?

• Nếu có thể, in ra Y.
• Nếu không thể, in ra N.

Input

• Dữ liệu gồm nhiều test và kết thúc bằng một dòng chứa 0 0.
  • Dòng đầu tiên của mỗi test chứa hai số nguyên ~K~ và ~M~ với:
    • ~K~ - số đứa trẻ ~(3 \le K \le 10^9)~.
    • ~M~ - số mong muốn ~(0 \le M \le 10^5)~.
  • ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~A~ và ~B~ ~(A, B \le K)~, mô tả rằng đứa trẻ ~A~ muốn ngồi cạnh đứa trẻ ~B~.

Output

• Với mỗi test (ngoại trừ dòng 0 0), in ra một dòng duy nhất:
  • Y nếu có thể sắp xếp thoả mãn mọi mong muốn.
  • N nếu không thể.

Sample Input

4 3
2 3
1 3
2 1
3 6
3 2
2 1
1 2
1 3
2 3
3 1
1 3
2 1
1000000000 0
0 0

Sample Output

N
Y
Y

Trong một buổi chiều dài lê thê, Dũng ngồi một mình với tâm trạng buồn chán. Để giết thời gian, cậu tìm thấy một xâu ký tự ~s~ gồm toàn các chữ cái tiếng Anh viết thường. Ban đầu, xâu ~s~ chẳng có gì đặc biệt với các ký tự trong xâu được đánh số từ ~1~ đến ~|s|~, nhưng rồi Dũng nảy ra một trò: cậu liên tục chọn một số nguyên ~a_i~ nào đó, rồi đảo ngược xâu con liên tiếp bắt đầu từ ký tự thứ ~a_i~ đến ký tự thứ ~|s| - a_i + 1~.

Dũng thực hiện trò chơi này tổng cộng ~m~ lần, mỗi lần với một giá trị ~a_i~ khác nhau (có thể trùng nhau). Cậu rất muốn biết, sau tất cả những lần đảo, xâu cuối cùng mà cậu thu được sẽ trông như thế nào. Nhiệm vụ của bạn là tìm giúp Dũng xâu kết quả đó.

Input

• Dòng đầu tiên: xâu ký tự ~s~ mà Dũng tìm được ~(2 \le |s| \le 2 \times 10^5)~.
• Dòng thứ hai: một số nguyên dương ~m~ ~(m \le 10^5)~ - số lần Dũng thực hiện thao tác đảo.
• Dòng thứ ba: gồm ~m~ số nguyên dương ~a_1, a_2, \dots, a_m~ ~(a_i \le \frac{|s|}{2}~), mỗi số mô tả một lần đảo xâu con từ ký tự thứ ~a_i~ đến ký tự thứ ~|s| - a_i + 1~.

Output

• In ra một dòng duy nhất chứa xâu ~s~ sau khi Dũng thực hiện lần lượt ~m~ lần đảo.

Sample Input 1

kcchinbayble
4
2 2 2 2

Sample Output 1

kcchinbayble

Sample Input 2

haideu
1
1

Sample Output 2

uediah

Just read only two integer numbers ~a~ and ~b~ ~(a, b \leq 10^{18})~ and print only one sum of those two numbers. Don't read another one!

Main Input

9 
7

Main Output

16