Checking Answers to Test

Interview

Time limit1sMemory limit512 MB

Summary

Given the correct answers and each student's answers, find every pair of students whose correct and incorrect answers each match on more than half of the questions.

Level: Medium4 of 10
Topics: Brute force, Implementation, Array, String
Solved: No attempts yet

Problem

Today the students had a test. The test consists of $n$ multiple-choice questions. Each question has four answer options "A", "B", "C" and "D", but only one of them is correct.

The teacher knows that the students often cheat. So he wants to find all pairs of students who have similar answers. Two students have similar answers if for each of them more than half of their correct answers match with the other student's answers, and more than half of their incorrect answers match with the other student's answers.

Help the teacher find all pairs of students who have similar answers to the test.

Input

The first line of input contains one integer $n$ denoting the number of questions in the test ( $1 \le n \le 100$ ).

The second line contains correct answers, they are represented by a string of length $n$ . The string consists of letters "A", "B", "C" and "D", the $i$ -th letter is the correct answer for the $i$ -th question.

The third line contains one integer $m$ denoting the number of students, who had the test today ( $1 \le m \le 100$ ).

Next $m$ lines contain students' answers in the same format as the correct answers. The $i$ -th line contains the answers given by the $i$ -th student.

Output

The first line of output must contain the number of pairs of students who have similar answers. The following lines must contain all such pairs of students, in any order. You can output the numbers in one pair in any order.

Examples2

Example 1
Input
```
3
AAA
4
ABA
ABA
CBA
CAA
```
Expected output
```
1
1 2
```

Example 2

Input

6
ABCDAB
3
ABCCCC
BBCDCC
ACCDCC

Expected output