avatarГость
← К соревнованиям

Олимпиада школьников "Innopolis Open"

КНБ-строка

Сложность: 58%

В Иннополисе новое соревнование: битва роботов в камень-ножницы-бумага. Правда все крутые роботы заняты полноценной работой, поэтому в боях участвуют самые простые боты. Каждый из них всегда выбрасывает что-то одно: камень, ножницы или бумагу.

image

Роботы стоят в линию. Дальше судья может выбрать два соседних робота, и заставить их сыграть один раунд в камень-ножницы-бумагу. Если один из них выиграл другого, то проигравший выбывает из игры и его убирают из списка роботов, оставшиеся роботы при этом не меняют свой порядок в линии. При этом есть две версии правил. В первой из них, если роботы показали одно и тоже, судья может самостоятельно выбрать, какого из них удалить из игры. Во второй же версии, если если роботы показали одно и тоже, оба робота остаются. Робот побеждает, если все остальные роботы выбыли из игры.

Однако судье стало очень скучно вести бои, поэтому он хочет для каждого робота узнать, может ли он так выбирать пары в каждом раунде, чтобы этот робот победил. Помогите ему решить эту задачу!

Входные данные

Вам нужно будет решить несколько тестов.

В первой строке задано целое число tt (t≥1t \ge 1) – число тестов во входных данных.

Далее заданы tt тестов, каждый из которых состоит из целого числа и строки.

Число dd обозначет версию правил, которая используется в текущей расстановке роботов d∈{1,2}d \in \{1, 2\}.

Дальше идёт строка ss, в которой записано nn (1≤n≤5⋅1051 \le n \le 5 \cdot 10^5) строчных букв английского алфавита r, p и s, описывающих список роботов. Точнее, символы r, p и s означают роботов, которые всегда показывают камень, бумагу и ножницы соответственно.

Сумма nn по tt заданным тестам не превосходит 5⋅1055 \cdot 10^5.

Выходные данные

Выведите tt строк: по одному для каждого теста.

Строка должна содержать nn цифр 0 и 1, для каждого ii от 1 до nn запишите 1, если судья может так выбирать пары для раундов, чтобы ii-й робот победил, и 0 в противном случае.

Подзадачи

№баллынеобх. подзадачиограничения
0

0

-

Тесты из условия

1

7

-

d=1,∑n≤20d = 1, \sum n \le 20

2

9

1

d=1,∑n≤200d = 1, \sum n \le 200

3

10

2

d=1,∑n≤5000d = 1, \sum n \le 5000

4

11

3

d=1,∑n≤5⋅105d = 1, \sum n \le 5 \cdot 10^5

5

7

1

∑n≤20\sum n \le 20

6

13

2, 5

∑n≤200\sum n \le 200

7

10

3, 6

∑n≤5000\sum n \le 5000

8

33

4, 7

∑n≤5⋅105\sum n \le 5 \cdot 10^5

STDINSTDOUT
4
1 rpspp
2 pps
1 rpsps
2 rpssprsrr
10111
001
10101
110010001

Примечание

Разберём первый тестовый пример: rpspp, d=1d = 1. Пронумеруем роботов от 1 до 5 слева направо.

  1. Для того чтобы остался робот с номером 1, судья может действовать следующим образом:

    • Судья выбирает роботов с номерами 4 и 5, они выбрасывают одно и тоже, поэтому судья решает что 5-й выбывает. Остаются роботы с номерами {1, 2, 3, 4}.

    • Судья выбирает роботов с номерами 2 и 3, 2-й выбывает. Остаются роботы с номерами {1, 3, 4}.

    • Судья выбирает роботов с номерами 3 и 4, 4-й выбывает. Остаются роботы с номерами {1, 3}.

    • Судья выбирает роботов с номерами 1 и 3, 3-й выбывает. Остался робот с номером 1.

  2. Для робота с номером 2, судья не может избавиться от 1-го робота, не удаляя 2-го, поэтому 2-й не может победить.

  3. Для того чтобы остался робот с номером 3, судья может действовать следующим образом:

    • Судья выбирает роботов с номерами 4 и 5, они выбрасывают одно и тоже, поэтому судья решает что 5-й выбывает. Остаются роботы с номерами {1, 2, 3, 4}.

    • Судья выбирает роботов с номерами 1 и 2, 1-й выбывает. Остаются роботы с номерами {2, 3, 4}.

    • Судья выбирает роботов с номерами 2 и 3, 2-й выбывает. Остаются роботы с номерами {3, 4}.

    • Судья выбирает роботов с номерами 3 и 4, 4-й выбывает. Остался робот с номером 3.

  4. Для того чтобы остался робот с номером 4, судья может действовать следующим образом:

    • Судья выбирает роботов с номерами 4 и 5, они выбрасывают одно и тоже, поэтому судья решает что 5-й выбывает. Остаются роботы с номерами {1, 2, 3, 4}.

    • Судья выбирает роботов с номерами 2 и 3, 2-й выбывает. Остаются роботы с номерами {1, 3, 4}.

    • Судья выбирает роботов с номерами 1 и 3, 3-й выбывает. Остаются роботы с номерами {1, 4}.

    • Судья выбирает роботов с номерами 1 и 4, 1-й выбывает. Остался робот с номером 4.

  5. Для того чтобы остался робот с номером 5, судья может действовать следующим образом:

    • Судья выбирает роботов с номерами 4 и 5, они выбрасывают одно и тоже, поэтому судья решает что 4-й выбывает. Остаются роботы с номерами {1, 2, 3, 5}.

    • Судья выбирает роботов с номерами 2 и 3, 2-й выбывает. Остаются роботы с номерами {1, 3, 5}.

    • Судья выбирает роботов с номерами 1 и 3, 3-й выбывает. Остаются роботы с номерами {1, 5}.

    • Судья выбирает роботов с номерами 1 и 5, 1-й выбывает. Остался робот с номером 5.

Разберём второй тестовый пример: pps, d=2d = 2. Пронумеруем роботов от 1 до 3 слева направо.

  1. Для робота с номером 1, судья не может избавиться от 2-го робота, не удаляя 1-го, поэтому 1-й не может победить.

  2. Для робота с номером 2, судья не может избавиться от 1-го робота, не удаляя 2-го, поэтому 2-й не может победить.

  3. Для того чтобы остался робот с номером 3, судья может действовать следующим образом:

    • Судья выбирает роботов с номерами 2 и 3, 2-й выбывает. Остаются роботы с номерами {1, 3}.

    • Судья выбирает роботов с номерами 1 и 3, 1-й выбывает. Остался робот с номером 3.