Background

Originally, this problem statement was related to "Meow Meow". But I heard some people thought the statement was too long, so let’s keep it short.

Problem Description

You are given a sequence of length $4n$, where each number from $1$ to $n$ appears exactly $4$ times. Determine whether it is possible to split it into two identical subsequences of equal length.

Input Format

The first line contains a positive integer $n$.

The second line contains $4n$ positive integers describing the sequence. It is guaranteed that each number from $1$ to $n$ appears exactly $4$ times.

Output Format

If it is impossible to split into two identical subsequences, output one line No.

Otherwise, output Yes on the first line. On the second line, output a 01 string of length $4n$. The $i$-th character indicates which subsequence the $i$-th number of the original sequence is assigned to. You must ensure that the two subsequences you obtain are exactly identical.

2
1 1 2 1 2 2 1 2

Yes
10000111

Hint

Sample Explanation 1

Both subsequences are $(1,2,1,2)$.

Subtasks

Constraints: $1\le n \le 5\times10^4$.

It is guaranteed that each number from $1$ to $n$ appears exactly $4$ times in the sequence.

Scoring

The first line of your output must match the standard answer. If it is Yes, any valid splitting is accepted.

Source

From the preliminary round of the 2023 Tsinghua University Student Algorithm and Programming Contest and Collegiate Invitational (THUPC2023).

Resources such as editorials can be found at https://github.com/THUSAAC/THUPC2023-Pre.

By E.Space: Since the testdata was too weak during the contest, the testdata for this problem has been strengthened.

Translated by ChatGPT 5