Description

Given a string S, you are going to shift part of it.
Specifically, a shift on a string is to move all the characters left but the leftmost characters would be move to the rightmost.
For example, a shift on "abcd" would result in "bcda".

This problem ask you implement a function shift(char *start, char *end) that shift a substring of S starting from start to end.

1.      This problem involves three files.

• function.h: Function definition of shift.
• function.c: Function implementation of shift.
• main.c: A driver program to test your implementation.

You will be provided with main.c and function.h, and asked to implement function.c.

• 2.     For OJ submission:

          Step 1. Submit only your function.c into the submission block. (Please choose c compiler) 

  Step 2. Check the results and debug your program if necessary.

Input

The first line is a string S. (length of S<=20)
The second is a integer n. (n<=10)
The next n lines, each contains two integers l and r.(l<=r<=n)
This means that a shift on S[l]S[l+1]...S[r].
If the length of substring is one(l=r), then you should keep the string unchanged.
All these shift must be done in order.

 

Output

The result string after all n shift operations.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11253.c

Partial Judge Header

11253.h

Tags

Discuss

Description

The floor in Winnie the Pooh’s house is made of N row *M column square woods,

When he cleaned the house, he observed that there are two types of wood — 'o' and '#' .

He wants to know the maximum number of consecutive woods with the same type in a row or column or diagonal of each type respectively.

Input

The first line you are given an integer T, means there will be T tests.(1<=T<=10).

Each test you are given integers N, M.

The next N lines contains M characters('o' or '#').

Note:

Testcase 1: (1 ≤ N, M , K≤ 1000) and the diagonal does not affect the answer.

Testcases 2~3: (1 ≤ N, M , K≤ 100).

Testcases 4~5: (1 ≤ N, M , K≤ 1000).

Output

Each test output the maximun number of consecutive  'o'  woods, the maximun number of consecutive  '#'  woods, and a new line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Honey Kingdom, a nation built by bees, all areas are developed in a regular hexagonal (正六邊形) pattern. To facilitate development, they use a unique coordinate system where each hexagonal cell is represented by coordinate (x,y) as shown below:

The map is structured such that the first row has coordinates:

(1,1) , (1,2) , ... , (1,M)

The second row then has:

(2,1) , (2,2) , ... , (2,M)

...

In this system, each cell (x,y) is positioned between (x−1,y) and (x−1,y+1).

For any cell located at (x,y), its neighboring cells are:

(x-1,y) , (x-1,y+1) , (x,y-1) , (x,y+1) , (x+1,y-1) , (x+1,y)

Now, Bee Agent User333 has been assigned T missions, each involving a different map. On each map, the starting point is always (1,1) and the destination is (N,M).

Each cell on the map contains specific information denoted by A_i,j​ :

• If A_i,j = 'X', the cell is mostly water. For safety reasons, User333 cannot travel across water.
• If A_i,j = '0', the cell is open grassland, which User333 can freely cross.
• If A_i,j​ is a number '2' or '3', it indicates the presence of a "magic circle" with a "teleport radius" A_i,j​. Standing on this magic circle allows the agent to teleport to any cell within A_i,j​ steps, ignoring obstacles like water while moving, but they cannot teleport directly onto water cells.

User333 needs to determine whether they can reach the destination on each map using only flight and magic circles.

Input

The first line of input contains a positive integer T, representing the number of maps.

For each map, the input is structured as follows:

• The first line contains two positive integers N and M, representing the map's size N × M.

• The next N lines each contain M entries:

  A_1,1 , A_1,2 , ... , A_1,M
  ​A_2,1 , A_2,2 , ... , A_2,M
• Each entry A_i,j can be:
  • 'X' for water (impassable),
  • '0' for open grassland (passable),
  • An integer between '2' and '3' for a magic circle with that radius.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N,M ≤ 500
• A_i,j ∈ { 'X'  , '0' , '2' , '3' }
• Each map has at most 100 magic circles.
• The starting point (1,1) and the destination (N,M) are guaranteed to be open grassland.

Subtasks

• Testcases 1~2: N = 1, and there is no magic circle in the map.
• Testcases 3~4: N = 1
• Testcases 5~6: there is no magic circle in the map.
• Testcases 7~8: N,M ≤ 10
• Testcases 9~10: No additional restrictions.

 

Output

For each map, output a single line containing "YES" if it is possible to reach the destination from the start point, and "NO" otherwise (without quotes).

Please remember to print "\n" at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss