Problem Description

Given permutations \( P=(P_1,P_2,\dots,P_N) \) and \( Q=(Q_1,Q_2,\dots,Q_N) \) of \( (1,2,\dots,N) \).

Fill each cell of an \( N \) x \( N \) grid with characters 0 or 1 such that all of the following conditions are met:

• Let \( S_i \) be the string obtained by concatenating the characters written in the \( i \)-th row from the 1st to the \( N \)-th column. Then, \( S_{P_1} < S_{P_2} < \dots < S_{P_N} \) lexicographically.
• Let \( T_i \) be the string obtained by concatenating the characters written in the \( i \)-th column from the 1st to the \( N \)-th row. Then, \( T_{Q_1} < T_{Q_2} < \dots < T_{Q_N} \) lexicographically.

It can be proven that for any \( P \) and \( Q \), there is at least one way to fill the grid that satisfies all the conditions.

What does "lexicographically \( X < Y \)" mean? For strings \( X=X_1X_2\dots X_{|X|} \) and \( Y=Y_1Y_2\dots Y_{|Y|} \), "lexicographically \( X < Y \)" means one of the following holds:

1. \( |X| < |Y| \) and \( X_1X_2\ldots X_{|X|} = Y_1Y_2\ldots Y_{|X|} \).
2. There exists an integer \( 1 \leq i \leq \min\{|X|, |Y|\} \) such that both of the following are true:
   - \( X_1X_2\ldots X_{i-1} = Y_1Y_2\ldots Y_{i-1} \)
   - \( X_i \) is less than \( Y_i \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( P_1 \) \( P_2 \) \( \dots \) \( P_N \) \( Q_1 \) \( Q_2 \) \( \dots \) \( Q_N \)

Output Format

Output a way to fill the grid that satisfies the conditions in the following format:

\( A_{11}A_{12}\dots A_{1N} \) \( \vdots \) \( A_{N1}A_{N2}\dots A_{NN} \)

If there are multiple valid ways to fill the grid, any of them will be considered correct.

Sample Input and Output

Sample Input #1

3
1 2 3
2 1 3

Sample Output #1

001
101
110

Sample Input #2

15
8 15 10 2 4 3 1 13 5 12 9 6 14 11 7
4 1 5 14 3 12 13 7 11 8 6 2 9 15 10

Sample Output #2

010001111110101
001000000101001
010001001100010
010000011110010
010011101101101
100101110100000
111100011001000
000001001100000
100011011000101
000111101011110
101010101010101
011010101011110
010011000010011
100110010110101
000101101100100

Notes/Hints

Constraints

• \( 2 \leq N \leq 500 \)
• \( P \) and \( Q \) are permutations of \( (1,2,\dots,N) \)
• All inputs are integers

Sample Explanation 1

In this input/output example, \( S_1 = \)001, \( S_2 = \)101, \( S_3 = \)110, and \( T_1 = \)011, \( T_2 = \)001, \( T_3 = \)110. Thus, \( S_1 < S_2 < S_3 \) and \( T_2 < T_1 < T_3 \) hold, satisfying the conditions.

见题面 Input 部分

见题面 Output 部分