Problem

Bộ phim Mưa Đỏ đang làm mưa làm gió hiện nay với số lượng người xem đông chưa từng có của lịch sử phim Việt tại rạp!! Tối nay chỉ còn một suất chiếu cuối cho bộ phim và bạn muốn đặt hai ghế ngồi cạnh nhau để xem cùng người yêu. Phòng chiếu có ~N~ hàng và ~M~ cột ghế:

• Ghế trống được ký hiệu 0.
• Ghế đã đặt được ký hiệu 1.

Bạn cần kiểm tra xem liệu có còn chỗ trống cho bạn và người yêu ngồi cạnh nhau không nhé! Nhanh lên kẻo cô ấy sẽ dỗi bạn đó.

Input

• Dòng đầu: số bộ test ~T~ ~(1 \le T \le 10^2)~.
• Với mỗi bộ test:
  • Dòng 1: hai số nguyên ~N, M~ ~(1 \le N, M \le 10^3)~.
  • ~N~ dòng tiếp theo: mỗi dòng chứa chuỗi gồm đúng ~M~ ký tự 0/1 (hoặc ~M~ số 0/1 cách nhau bởi khoảng trắng) mô tả trạng thái từng ghế của hàng đó.

Output

Với mỗi bộ test, in một dòng:

• 'YES' nếu tồn tại cặp ghế trống kề ngang trong cùng một hàng,
• 'N0' nếu không tồn tại.

Sample

Problem

Tại biên cương lục địa Arvion, mỗi Vương Thú canh giữ một chiếc ấn tín. Tương truyền, ấn tín của Vương Thú thứ ~i~ chứa đựng lực quy tụ đúng bằng tổng mọi cống vật mà các bộ tộc từng dâng lên nó suốt ngàn năm.

Người ta ghi nhận rằng mỗi một cống vật của Vương Thú thứ ~i~ sẽ là các ước số nguyên dương khác nhau của ~i~.

Lực quy tụ của ấn tín ~i~ chính là tổng tất cả các cống vật hợp lệ ấy.

Bạn nhận được một danh sách các ấn tín cần thẩm định. Hãy cho biết lực quy tụ của mỗi ấn tín trong danh sách.

Input

• Dòng thứ nhất chứa số nguyên ~q~ — số ấn tín cần thẩm định.
• Dòng thứ hai chứa ~q~ số nguyên dương ~a_1, a_2, \ldots, a_q~ — chỉ số các Vương Thú.

Output

In ra một dòng gồm ~q~ số, trong đó số thứ ~i~ là ấn tín mang chỉ số ~a_i~. Các số cách nhau bởi một khoảng trắng.

Constraints

• ~1 \le q \le 10^7~
• ~1 \le a_i \le 10^{12}~

Sample

Problem

Trong đám cưới cổ tích của nhà Florendale, đại sảnh bày một tháp ly champagne lấp lánh.
Đỉnh tháp là một chiếc ly duy nhất ký hiệu ~(0,0)~ (tầng 0). Tháp có ~n~ tầng, tầng dưới nhiều hơn tầng trên 1 ly. Mỗi ly dung tích đúng 1.

Nghi lễ rót rượu bắt đầu: cô dâu chú rể lần lượt rót ~m~ chai champagne (mỗi chai thể tích 1 đơn vị) vào chiếc ly trên đỉnh. Khi một ly đầy, phần trào từ ly ấy được chia đều cho hai ly ngay bên dưới (trái và phải), rồi tiếp tục như thế qua các tầng dưới cho tới khi rượu ngừng chảy.

Hãy cho biết sau nghi lễ, ly ~(i, j)~ chứa bao nhiêu rượu.

Input

• Dòng đầu: số bộ test ~T~ ~(0 \le T \le 10)~.
• Mỗi bộ test gồm một dòng chứa 3 số nguyên ~m, i, j~:
  • ~m~: số chai rót vào ly đỉnh,
  • ~i, j~: vị trí ly cần hỏi với ~0 \le j \le i \le n~.

Output

Với mỗi test, in một dòng là lượng champagne trong ly ~(i, j)~ sau khi dòng chảy ổn định, làm tròn tới 5 chữ số thập phân.

Constraints

• ~0 \le m \le 10^9~
• ~0 \le i \le n \le 10^5~
• ~0 \le j \le i~

Sample

Note:

• Giải thích test 1:

• Có 2 chai rượu và tháp cưới 2 tầng. Cốc đầu tiên (0, 0) được đổ đầy

• Rượu cốc (0, 0) thừa chảy xuống đều cho 2 cốc ở dưới (1, 0) và (1, 1)

• Như vậy thì cốc (1, 1) được đổ đầy là 1/2 = 0.50000

• Giải thích test 2: Vì tất cả các cốc đều được đổ đầy nên cốc cần xét được đổ đầy = 1.00000

Problem

Trên quảng trường lễ hội, các hội đoàn bày một dãy quân trụ lễ (như quân cờ domino) thẳng hàng, đánh số từ trái sang phải ~1, 2, \ldots, n~. Mỗi quân trụ có thể được phù thủy gió hô nghiêng về trái hoặc hô nghiêng về phải; những quân không bị gọi sẽ đứng yên.
Sau hồi trống, phép gọi đồng thời phát tác:

• Nếu một quân trụ nghiêng sang trái, nó lập tức xô quân trụ kề bên bên trái (nếu quân ấy vẫn đứng), rồi sức xô truyền tiếp từng bước về trái.
• Tương tự, quân nghiêng sang phải xô về phía bên phải.
• Nếu tại một thời điểm hai luồng xô cùng chạm tới cùng một quân từ hai phía đối nghịch, quân đó giữ thăng bằng và đứng yên.

Bạn được cho trạng thái gọi ban đầu của ~n~ quân trụ. Sau khi hiệu ứng kết thúc, có bao nhiêu quân trụ vẫn đứng yên?

Input

• Dòng đầu: số bộ test ~T~ ~(1 \le T \le 10^3)~.
• Với mỗi test:
  • Dòng 1: số nguyên ~n~ ~(1 \le n \le 10^5)~ — số quân trụ.
  • Dòng 2: một chuỗi dài ~n~ ký tự mô tả lệnh gọi ban đầu:
  • 'L': quân trụ bị gọi nghiêng về trái,
  • 'R': quân trụ bị gọi nghiêng về phải,
  • '.': quân trụ không bị gọi.

Tổng độ dài của tất cả chuỗi trong dữ liệu không vượt quá ~10^5~.

Output

Với mỗi test, in một số nguyên — số quân trụ đứng yên sau khi mọi hiệu ứng kết thúc.

Sample

Problem

In ra ma trận xoắn ốc cấp ~N~, với các số trong ma trận đều là các số trong dãy Fibonacci.

Input

• Một dòng duy nhất chứa số nguyên ~N~.

Output

In ra ma trận xoắn ốc cấp ~N~ với các phần tử là các số Fibonacci, mỗi hàng trên một dòng, các phần tử cách nhau một dấu cách.

Constraints

• ~1 \le N \le 9~

Sample

Problem

Ở Yến Hội Mặt Nạ tại thành phố Lysandre, người dự tiệc phải được chia vào hai đại sảnh sao cho bầu không khí vẫn lạ lùng, khó đoán như lời tiên tri yêu cầu. Quy tắc của chủ tiệc:
Bất kỳ hai người đã quen nhau không được ở cùng một sảnh.
(nghĩa là trong mỗi sảnh, mọi cặp người bất kỳ đều không quen biết nhau).

Bạn được trao một bảng quan hệ quen biết của ~N~ người, dưới dạng ma trận đối xứng kích thước ~N \times N~ với các phần tử là 0 hoặc 1:

• A[i][j] = 1 nếu người ~i~ quen người ~j~,
• A[i][j] = 0 nếu họ không quen.

Hãy xác định xem có thể chia tất cả khách mời vào hai sảnh thỏa quy tắc trên hay không.

Input

Gồm nhiều bộ test. Mỗi bộ test có dạng:

• Dòng đầu: số nguyên dương ~n~ ~(1 \le n \le 100)~ — số người.
• ~n~ dòng tiếp theo: dòng thứ ~i~ chứa ~n~ số 0/1 mô tả hàng ~i~ của ma trận ~A~.

Dữ liệu đảm bảo: ~A[i][j] = A[j][i]~, ~A[i][i] = 0~.

Output

Với mỗi bộ test, in một dòng:

• YES nếu có cách chia vào hai sảnh thỏa yêu cầu,
• N0 nếu không thể.

Sample

Problem

Tại hầm mộ của vương triều cổ, bạn đứng trước một mê cung lát đá hình lưới có ~N~ hàng và ~M~ cột. Mỗi ô khắc một con số thể hiện năng lượng bạn thu được khi đặt chân lên đó.
Bạn khởi hành từ ô ~[1,1]~ và mục tiêu là ô ~[N,M]~. Lời nguyền của hầm mộ chỉ cho phép bạn đi sang phải hoặc đi xuống mỗi bước.
Hãy tìm Lối Vàng – con đường giúp tổng năng lượng thu được lớn nhất từ ~[1,1]~ đến ~[N,M]~.

Input

• Dòng đầu: hai số nguyên ~N, M~.
• ~N~ dòng tiếp theo, mỗi dòng gồm ~M~ số nguyên ~A[i][j]~ — năng lượng tại ô hàng ~i~, cột ~j~.

Output

In ra tổng năng lượng lớn nhất có thể đạt được khi đi từ ~[1,1]~ đến ~[N,M]~ theo các quy tắc di chuyển.

Constraints

• ~1 \le N, M \le 100~
• ~1 \le A[i][j] \le 10^9~

Sample

Problem

Sau khi Nữ Thần Mùa Xuân biến mất, Vương điện Laucaria mở Mê Lộ Bích Họa – một cung điện phẳng gồm ~n~ hàng và ~m~ cột. Tế quan phải lần theo đường đi đã khắc sẵn trên nền đá theo kiểu con rắn. Biết rằng mỗi bước đi đều mất ~k~ đồng tế phẩm.

Trên mỗi ô có thể ẩn một bùa chú độc. Bảng nghi thức ghi bằng chữ cổ: trên đường đi, hễ đặt chân lên ô có bùa độc thì phải quay về Đài Tẩy Uế gần nhất trước đó để làm lễ để hóa giải (khi làm lễ thì không mất tiền). Đài Tẩy Uế luôn nằm ở đầu của một hàng mà đã đến.

Hãy tính tổng chi phí tế phẩm tối thiểu để hoàn thành nghi thức cho toàn bộ mê lộ.

Chú ý: Tế quan sẽ đi theo kiểu con rắn tức là đi hết hàng 1, rồi đi đến cuối hàng 2, rồi lên đầu hàng 2, rồi sang đầu hàng 3... Khi tế quan tới hàng chẵn mà đang nhiễm bùa độc, thì tế quan chưa biết rằng có bùa độc nữa ở đằng trước không nên sẽ về hàng trước chữa trị. Ở các hàng lẻ thì tế quan sẽ luôn về đầu hàng để chữa trị.

Input

Dòng đầu là số bộ test ~t~.
Mỗi test gồm một dòng chứa ba số nguyên ~n, m, k~ ~(1 < n, m, k < 100)~.
Tiếp theo là ~n~ dòng, mỗi dòng có ~m~ ký tự 0 hoặc 1:

• 0 nghĩa là ô an toàn,
• 1 nghĩa là ô có bùa độc.

Output

Với mỗi test, in ra tổng chi phí tế phẩm cần thiết để đi theo lộ trình hình rắn và hoàn tất nghi thức.

Sample