Description

CSSA (資工系學會) is going to hold a BBQ party. The student enrollment is very high, yet the space is limited. So CSSA sorted the students with the special priority and the students with higher priority will be invited first. The priority is determined by the following rules:

1. The students who have paid the membership fee will have higher priority than those who haven't.
2. The junior students will have higher priority than the senior students.
3. The students who registered as a group will have higher priority than those who registered individually.

These rules are applied in the order of 1, 2, 3. Which means if two students have the same priority in rule 1, then we will compare their priority in rule 2, and if they still have the same priority, then we will compare their priority in rule 3. If they have the same priority in all the rules, then we will consider them as the same priority.

CSSA has all the registration information of the students in the order of registration time. Dogeon (鴿子) sorted them with the priority mentioned above. But then Stiff Waist Beast (挺腰獸) told Dogeon that he should sort the students with stable sorting algorithm. But Dogeon isn't sure if the sorting algorithm he used is stable or not. Help Dogeon to check if the sorting algorithm he used is stable or not.

Stable sorting algorithm: A sorting algorithm is said to be stable if and only if two elements with equal priority appear in the same order in the sorted output as they appear in the input array to be sorted.

• For C, you can use strcmp function to compare two strings.

#include <string.h>
int sameName(const char *a, const char *b) {
    return strcmp(a, b) == 0;
}

The function strcmp compares two strings lexicographically. It returns zero if the strings are equal, a negative value if the first string is lexicographically less than the second string, and a positive value if the first string is lexicographically greater than the second string.

• For C++, you can directly use the == operator to compare two std::string.

#include <string>
bool sameName(const std::string &a, const std::string &b) {
    return a == b;
}

• For those who write in C++, you can add the following code at the beginning of the main function to speed up the input and output:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Note: The purpose of ios_base::sync_with_stdio(false); is to unsynchronize the C and C++ standard streams. By default, all standard streams are synchronized, which means that C++ standard streams are tied to their respective C streams. After adding ios_base::sync_with_stdio(false);, you should use cin and cout for input and output. Do not use scanf and printf anymore.

Input

The first line of the input contains an integer \(t\), the number of sub-tasks. Followed by \(t\) sub-tasks. The description of each sub-task is as follows.

For each sub-task, the first line contains an integer \(N\), the number of students. Following \(N\) lines contain the information of the students \(a_i\) in the order of registration time. Following another \(N\) lines contain the information of the students \(b_i\) sorted by Dogeon.

\(N\)
\(a_1\)
\(a_2\)
\(\vdots\)
\(a_N\)
\(b_1\)
\(b_2\)
\(\vdots\)
\(b_N\)

The information of a student contains four parts: the name of the student \(S_i\), the grade of the student \(G_i\), the registration type of the student \(T_i\) (0 for individual, 1 for group), and the payment status of the student \(P_i\) (0 for unpaid, 1 for paid). The information is separated by a space.

\(S_i \quad G_i \quad T_i \quad P_i\)

Constraints

• \(1 \leq t \leq 10^5\)
• \(1 \leq N \leq 5 \times 10^6\)
• \(1 \leq \sum N \leq 5 \times 10^6\)
• \(1 \leq |S_i| \leq 20\)
• \(1 \leq G_i \leq 5\)
• Name of the student contains only lowercase and uppercase letters.
• None of the students have the same name.
• \(b_i\) is a permutation of \(a_i\), which means for each \(i\), there exists a unique \(j\) such that \(a_i = b_j\), and vice versa.
• \(b_i\) is sorted in the order of priority mentioned above.

1. For test case 1 ~ 4, \(\sum N \leq 10^3\)
2. For test case 5 ~ 8, \(\sum N \leq 2 \times 10^5\)
3. For test case 9 ~ 10, \(\sum N \leq 5 \times 10^6\), your time complexity might need to be \(O(N)\) to pass these two test cases.

Output

Output \(t\) lines. For each sub-task, output "YES" if the sorting algorithm is stable, and "NO" otherwise.

Sample Input  Download

Sample Output  Download

Tags

Discuss