Cho ma trận A[][] cỡ NxM gồm N hàng, mỗi hàng M cột. Nhiệm vụ của bạn là hãy cho tất cả các phần tử thuộc hàng I và cột J của ô (I, J) thành số 28 nếu ô A[i][j] = 28.

Đầu vào

Dòng đầu tiên là 2 số N và M.

N dòng tiếp theo mỗi dòng có M số.

Giới hạn

1≤N,M≤1000

0<=A[i][j]<=1000

Đầu ra

In ra ma trận sau khi thay đổi

Ví dụ :

Input 01

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

Output 01

4 1 28 28 3 4 
1 7 28 28 6 6 
7 8 28 28 6 3 
28 28 28 28 28 28 
9 9 28 28 8 8

Cho ma trận vuông cấp N gồm N hàng và N cột, mỗi ô trên ma trận chứa 1 chữ cái là chữ in hoa hoặc in thường.

Bạn hãy xác định xem trên ma trận này có ma trận con cỡ 3x3 nào chứa đủ hết mọi chữ cái trong từ 28tech hay không? Nếu có in ra 28tech, ngược lại in ra 29tech. Lưu ý là các ký tự in hoa hay in thường đều được chấp nhận.

Đầu vào

Dòng 1 là N

N dòng tiếp theo chứa N ký tự của ma trận

Giới hạn

1<=N<=500

Các ký tự trong ma trận là chữ cái hoặc chữ số

Đầu ra

In ra kết quả của bài toán

Ví dụ :

Input 01

6
c z x 2 w 2
h 3 u e d t
1 b d h w 1
3 r q 2 i h
c m l c k 1
p n o 8 T e

Output 01

28tech

Cho 1 bảng số có N dòng, mỗi dòng có không quá M số, 28tech muốn bạn chỉ ra giá trị nằm tại hàng x và cột y của bảng số này.

Bạn cần trả lời nhiều truy vấn.

Đầu vào

Dòng 1 là N : số lượng dòng của bảng số

N dòng tiếp theo mô tả thông tin của mỗi dòng trên bảng số, trong đó số đầu tiên của mỗi dòng là m : số lượng số của dòng đó, m số tiếp theo được viết cách nhau 1 khoảng trắng

Dòng tiếp theo là số truy vấn Q

Q dòng tiếp theo mỗi dòng là 1 truy vấn gồm 2 số x, y

Giới hạn

1<=N<=500

1<=m<=M<=500

1<=Q<=1000

1<=x<=N

1<=y<=m

Đầu ra

Đối với mỗi truy vấn in ra số thuộc hàng x, cột y của bảng số.

Ví dụ :

Input 01

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

Output 01

8
5
6
6

28Tech cho bạn cách mã hóa các số nguyên bằng cách thay nó bằng các dấu đóng mở ngoặc tròn với quy luật như sau : Số 0 tương đương với tập rỗng là (), các số > 0 sẽ là tập hợp tất cả các số nhỏ hơn nó viết liền nhau theo thứ tự từ bé đến lớn, ví dụ số 3 sẽ được viết (0,1,2) trong đó 0, 1, 2 ở dạng mã hóa. Vì thế ta sẽ được

Số 0 : ()

Số 1 : (())

Số 2 : ((),(()))

Số 3 : ((),(()),((),(())))

Số 4 : ((),(()),((),(())),((),(()),((),(()))))

28Tech cho bạn 2 số x, y dưới dạng được mã hóa, hãy in ra tổng 2 số dưới dạng mã hóa, biết rằng tổng của 2 số không vượt quá 15.

Đầu vào

Dòng 1 gồm số bộ test T

2T dòng tiếp theo mỗi test gồm 2 dòng tương ứng với 2 số x, y

Giới hạn

1<=T<=100

0<=x,y<=15

Đầu ra

In ra kết quả mỗi test trên 1 dòng

Ví dụ :

Input 01

5
()
((),(()))
()
((),(()))
((),(()))
(())
()
()
((),(()),((),(())),((),(()),((),(()))))
()

Output 01

((),(()))
((),(()))
((),(()),((),(())))
()
((),(()),((),(())),((),(()),((),(()))))

Hôm nay Tý đi xem phim tại rạp chiếu phim cùng bạn Tèo, Tèo biết Tý là một sinh viên IT đang học những bài học về chuỗi ký tự. Tèo muốn Tý tìm ra xâu con các ký tự (không cần liên tiếp) từ tên của bộ phim 2 bạn xem ngày hôm nay sao cho xâu con đó có thứ tự từ điển lớn nhất. Tý thì cũng chỉ mới học về chuỗi ký tự nên kỹ năng lập trình còn chưa vững nên muốn nhờ bạn giúp tìm ra xâu con lớn nhất đó. Bạn hãy giúp Tý tìm ra xâu con mà Tèo yêu cầu nhé.

Đầu vào

Dòng duy nhất chứa tên của bộ phim.

Giới hạn

Tên của bộ phim là chuỗi ký tự chỉ bao gồm ký tự in hoa hoặc in thường, độ dài của tên bộ phim không vượt quá 2.10^5 ký tự.

Đầu ra

In ra xâu con có thứ tự từ điển lớn nhất. Lưu ý là xâu con này không nhất thiết phải chứa các ký tự liên tiếp

Ví dụ :

Input 01

bbbbccccddaddczaabbcd

Output 01

zd

Cho ma trận cỡ NxM gồm N hàng, mỗi hàng M cột. Mỗi ô trên ma trận có giá trị là 1 hoặc 0, 1 tương ứng với đường đi và 0 tương ứng với vật cản.

Hãy đếm số cách đi từ ô (1, 1) tới ô (N, M) biết rằng ở mỗi bước đi bạn chỉ có thể đi vào ô không có vật cản nằm bên dưới hoặc bên phải ô hiện tại. Dữ liệu đảm bảo kết quả nằm trong giới hạn của số nguyên 64 bit.

Đầu vào

Dòng đầu tiên là 2 số N và M. N dòng tiếp theo mỗi dòng có M số.

Giới hạn

1≤N,M≤100

0<=A[i][j]<=1

Đầu ra

In ra đáp án của bài toán

Ví dụ :

Input 01

3 3
1 1 1
1 0 1
1 1 1

Output 01

2

Cho một bảng số cỡ N hàng và M cột, trên mỗi ô của bảng số có ghi một số nguyên X, Tèo yêu thích các ô trên bảng có cùng giá trị X và nằm cạnh nhau vì thế anh ta nhờ bạn xác định các ô cạnh nhau (chung đỉnh) mà có cùng số ghi trên đó. Tèo coi diện tích một vùng các ô liền kề là số lượng các ô nằm cạnh nhau (chung đỉnh) mà chúng có cùng giá trị của X.

Bạn hãy giúp Tèo liệt kê các giá trị khác nhau xuất hiện trên bảng số theo thứ tự tăng dần và với mỗi giá trị đó bạn hãy liệt kê diện tích các vùng chứa giá trị này theo diện tích tăng dần.

Ví dụ trong hình trên có :

• 3 vùng số 1 với diện tích là 1, 3, 6

• 2 vùng số 2 với diện tích là 3, 6

• 2 vùng số 3 với diện tích là 1, 5

Đầu vào

• Dòng 1 là N và M

• N dòng tiếp theo mỗi dòng gồm M số nguyên X

Giới hạn

• 1<=N,M<=50

• -100<=X<=100

Đầu ra

In ra đáp án của bài toán, với mỗi dòng in ra giá trị và diện tích các cùng chứa giá trị này theo thứ tự tăng dần

Ví dụ :

Input 01

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

Output 01

1 : 1 2 2 
2 : 1 1 1 1 1 
3 : 1 4 4 
4 : 1 2 3

28Tech lớn lên trong 1 dòng họ mà ở đây họ đặt tên cho những người trong dòng họ phải tuân theo một quy tắc, theo trưởng họ thì điều này sẽ làm gia phả của dòng họ trở nên đẹp hơn. Quy tắc đặt tên ở đây là tên của một người bất kỳ tròng dòng họ không được là phần đầu trong tên của 1 người khác nào đó trong dòng họ.

Ví dụ dòng họ có 3 người tên 28techa, 28tech@#a, 28tet là chuẩn quy tắc, trong khi đó nếu dòng họ có 3 người tên 28tech, 28tech@ và 28tech28tech lại không phải là chuẩn quy tắc. Vì 28tech là phần đầu của 28tech@ hoặc 28tech28tech.

Cho danh sách tên người trong dòng họ của 28Tech, bạn hãy in ra 28tech nếu dòng họ đã đặt tên đúng quy tắc, ngược lại bạn cần in ra 29tech.

Đầu vào

Dòng đầu tiên chứa số N - số lượng tên người trong dòng họ

N dòng tiếp theo chứa tên 1 người trong dòng họ là chuỗi không có dấu cách và không quá 100 ký tự.

Giới hạn

1<=N<=10^5

Đầu ra

In ra 28tech hoặc 29tech.

Ví dụ :

Input 01

3
aabc
aabbb
az

Output 01

28tech

Input 02

3
28t
28techtech
28th

Output 02

29tech

Hệ số nhị phân và hệ thập lục phân (16) là 2 hệ số yêu thích của 28Tech, ngoài ra 28Tech cũng yêu thích những số lớn nữa. Bây giờ 28Tech cung cấp cho bạn 1 mảng 2 chiều nhị phân cỡ N hàng và N cột bao gồm các số 0 và 1, bạn xuất phát từ ô (1, 1) và tìm đường đi tới ô (N, N), tại mỗi lần di chuyển bạn được đi từ ô hiện tại xuống dưới hoặc sang phải. Nghĩa là nếu bạn đang ở ô (i, j) thì bạn có thể đi xuống ô (i + 1, j) hoặc ô (i, j + 1).

Trên đường đi đó bạn sẽ lấy các số 0 hoặc 1 tại ô bạn đi qua và khi đó bạn sẽ tạo được một số nhị phân có độ dài 2*N - 1, nhiệm vụ của bạn là hãy tìm cách đi tạo ra số nhị phân lớn nhất và in ra nó dưới dạng hệ số 16.

Ví dụ trong mảng 2 chiều này cách đi tạo ra số nhị phân lớn nhất là 1111011 tương ứng với số 123 trong hệ thập phân và 7B trong hệ 16, vì thế bạn cần in 7B

Đầu vào

Dòng đầu tiên chứa số N

N dòng tiếp theo mỗi dòng chứa N số của ma trận

Giới hạn

1<=N<=100

Đầu ra

In ra số nhị phân lớn nhất tạo thành ở hệ 16.

Ví dụ :

Input 01

8
1 0 0 1 0 0 0 0 
0 0 0 0 0 1 1 0 
0 1 1 0 0 0 1 1 
1 1 0 1 0 0 0 0 
1 1 0 0 0 0 1 1 
0 1 1 0 1 0 0 1 
0 1 1 0 1 1 0 0 
0 1 1 1 1 0 0 1

Output 01

4FF9

Input 02

5
1 1 0 0 0 
1 1 0 0 0 
1 1 0 0 0 
0 1 0 1 0 
1 0 0 1 1

Output 02

1F7

28Tech rất thích nuôi chó nhưng bạn biết đấy trong 1 ngày thì những con chó trong nhà của 28Tech kêu không mỏi mồm và hay đánh chửi nhau. 28Tech có nuôi rất nhiều chó, chúng được đánh số thứ tự từ 0 và đặc biệt là chúng rất khó chịu khi có một con chó khác kêu nhiều hơn mình. Theo thứ tự thì con chó số 0 sẽ kêu g o o, con chó số 1 sẽ không chịu kém cạnh con chó số 0 và nó sẽ kêu dài hơn, nó muốn nó kêu nhiều gấp đôi còn chó xếp trước nó và còn hơn thế nữa. Nên con chó thứ 1 sẽ kêu g o o g o o o g o o

Quy luật tóm lại như sau :

Con chó số 0 sẽ kêu tương ứng với xâu D(0) = g o o

Con cho thứ k sẽ kêu tương ứng với xâu D(k) = D(k - 1) + g o o ... + D(k - 1), trong đó cụm g o o ... sẽ gồm 1 chữ g và k + 2 chữ o. Phép cộng ở đây tưng ứng với phép nối chuỗi.

Vậy ta sẽ có

D(0) = g o o

D(1) = g o o g o o o g o o

D(2) = g o o g o o o g o o g o o o o g o o g o o o g o o

....

28Tech rất mệt mỏi vì chúng không chịu nhường nhịn nhau, cách duy nhất để chúng im lặng là 28Tech phải trả lời cho Buck - con chó đầu đàn rằng ký tự thứ K xuất hiện trong 1 xâu nào đó tương ứng với tiếng kêu của 1 con chó bất kỳ trong đàn là ký tự nào? Dù biết nó chỉ có thể là chữ g hoặc chữ o nhưng 28Tech không thể đoán bừa được, bạn hãy giúp 28Tech tìm ra ký tự thứ K đó nhé.

Đầu vào

Dòng đầu tiên là số bộ test T

T dòng tiếp theo mỗi dòng chứa số nguyên K

Giới hạn

1<=T<=100

1<=K<=10^18

Đầu ra

In ra ký tự tìm được

Ví dụ :

Input 01

8
22
26
13
10
25
19
27
21

Output 01

o
g
o
o
o
g
o
o

Input 02

2
11
8

Output 02

g
g