Description

Given a dictionary with n words, such as A1, A2, ..., An, and a string B for searching. If B is a substring of Ai, then Ai is one of the word that we want to search. Find out all the words we want to search.

Note that all the words in dictionary and the string B contain only uppercase or lowercase alphabets. And when searching, uppercase letters are considered the same as lowercase letters, for example, we can use 'the' to find 'THE'.

Input

The first line of the input is an integer n (0<n≦1000).

For the next n lines, each line contains a string Ai (0<length of Ai≦100) and a ‘\n’ at the end of the line.

The last line contains the string B (0<length of B≦10).

Output

Print out all the searched words in their original order in dictionary. Note that you NEED to print ‘\n’ at the end of all the words.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Write a program that simulates a mouse in a maze. The program must count the steps taken by the mouse from the starting point to the final point.

The maze type is shown in following figure:

S$###
$$#$$
$$$##
##$$F

it consists of S (starting point), #(walls), $(road) and F (final point).

In above case, it needs 7 steps from S to F as following figure,

S$###
$$#$$
$$$##
##$$F

and the mouse can move in the four directions: up, down, left, right. There may be more than one way to reach final point, the program only need to print the least steps.

If there is no way from S to F, then print -1.

Input

The first line has an integer N(1<=N<=10^6), which means the number of test cases.

For each case, the first line has two integers. The first and second integers R and C (3<=R, C<=500) represent the numbers of rows and columns of the maze, respectively. The total number of elements in the maze is thus R x C.

The following R lines, each containing C characters, specify the elements of the maze.

Output

Print out the least steps for each case, and there is a new line character at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a matrix A (you can consider it as a 2-D array), print out transpose of A.

Note: Try to use dynamic memory management to finish this problem.

main.c

#include <stdio.h>

#include "function.h"


int main(void) {


  int **mat;

  int m, n;


  scanf("%d %d", &m, &n);


  mat = allocateMat(m, n);

  readInput(mat, m, n);

  printResult(mat, m, n);


  // Be sure to release acquired memory space

  for(i=0; i<m; i++)
    free(mat[i]);
  free(mat);

  return 0;

}

function.h

#ifndef FUNCTION_H

#define FUNCTION_H


int** allocateMat(int, int);

void readInput(int**, int, int);

void printResult(int**, int, int);


#endif

Input

First line has two integers, indicates A is M rows by N columns. Next M lines are the content of A, each line has N integers

Output

N lines, each line contains M integers. Values are separated by a blank. There’s a blank and a newline at the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

The kingdom of far worse is in trouble.

The enemies are going to attack kingdom of far worse.

The enemies have map of kingdom of far worse. The map shows that there are exactly some cities.

They are planning to isolate some cities of kingdom of far worse and their method is bomb some roads.

For example, there is a road between city 2 and city 3.

If the position of a bomb is (2, 3), the road from city 2 to city 3 will be destroyed by the bomb but there is still a road from 3 to 2.

The king of kingdom of far worse request you to write a program to show that which city does NOT have road can leave or enter it.

Note:

Below is a real map and its representation of 2-D array. Left-up is (1, 1).

For example of left part.

(1, 4) is 1, means there is a road from 1 to 4.

(4, 3) is 1, means there is a road from 4 to 3

(1, 2).is 0, means there is NO road from 1 to 2.

Input

One number N, N is the number of cities. 2 <= N <= 50

Following is a 2-D array map with N columns and N rows.

One number B, B is the number of bombs. 1 <= B <= N2

Following is B lines, each line is the position of bomb.

Output

Which city does NOT have road can leave or enter it.

The order of number is increasing. Each number is printed by format "%d\n" 

Sample Input  Download

Sample Output  Download

Tags

Discuss