Перестirməni tapın

Verilmiş $n$ ($n$ iki qüvvəti) ədədlərindən ibarət bir permütasiya var. Permütasiyadakı elementlərin sırası sizə məlum deyil.

Permütasiya, $1$-dən $n$-ə qədər olan tam ədədlərin uzunluğu $n$ olan bir ardıcıllığıdır və burada bütün ədədlər yalnız bir dəfə rast gəlinir. Məsələn, $[1]$, $[4,3,5,1,2]$, $[3,2,1]$ permütasiyalardır, lakin $[1,1]$, $[4,3,1]$, $[2,3,4]$ deyil.

Həmçinin belə bir sorğu var: siz $n$ uzunluğunda $a$ massivini verirsiniz, burada $1\le a_i\le n$ (qeyd edin ki, $a$ mütləq permütasiya deyil). Cavab olaraq, aşağıdakı qaydaya görə yaradılan $n$ uzunluğunda $c$ massivini alırsınız:

c = sıfırlardan ibarət n uzunluğunda massiv
for i = 1 to n:
    if p[a[i]] > p[i]:
         c[a[i]] += 1
c-ni qaytar

Sizdən tələb olunan, verilmiş permütasiyanı $p$ tapmaqdır. Maksimum sorğu sayını "Qiymətləndirmə" bölməsində baxın.

Giriş verilənləri

Birinci sətir iki tam ədəd $t$ və $q$ ($1\le t,q\le 256$) ehtiva edir — verilənlər dəstlərinin sayı və hər bir verilənlər dəstində istifadə edilə biləcək maksimum sorğu sayı.

Qarşılıqlı təsir

Hər bir verilənlər dəsti üçün əvvəlcə bir tam ədəd $n$ ($1\le n\le 1024$) oxuyun — permütasiyadakı $p$ elementlərinin sayı.

Zəmanət verilir ki, $n$ iki qüvvətidir (yəni elə bir tam qeyri-mənfi $k$ ədədi var ki, $2^k=n$).

Sorğu etmək üçün «1 $a_1$ $a_2$ ...$a_n$» ($1\le a_i\le n$) çıxış edin.

Sorğuya cavab olaraq, münsiflər proqramı şərtdəki qaydaya görə əldə edilən $c$ massivini belə bir formatda çıxış edəcək: «$c_1$ $c_2$ ...$c_n$».

Sorğunu çıxış etdikdən sonra yeni sətir simvolunu çıxış etməyi və çıxış buferini sıfırlamağı unutmayın. Əks halda, Vaxt limiti aşdı qərarını alacaqsınız. Buferi sıfırlamaq üçün istifadə edin:

• C++-da fflush(stdout) və ya cout.flush();

• Java-da System.out.flush();

• Pascal-da flush(output);

• Python-da stdout.flush();

digər dillər üçün sənədlərə baxın.

Qeyd edin ki, əgər sorğunuz etibarsızdırsa (sorğu limiti aşılmış və ya giriş massivi məhdudiyyətlərə uyğun gəlmir), interaktor «-1» çıxış edəcək və işini dayandıracaq. Əgər «-1» oxusanız, dərhal proqramınızı dayandırın ki, Yanlış cavab qərarını alasınız, əks halda təsadüfi bir qərar ala bilərsiniz.

Permütasiyanı $p$ tapdığınız zaman «2 $p_1$ $p_2$ ...$p_n$» çıxış edin.

Bundan sonra, əgər bu son verilənlər dəsti idisə, proqramınızı dayandırmalısınız, əks halda növbəti verilənlər dəsti ilə davam etməlisiniz.

Nümunələr

1 256
4

0 1 1 1

1 3 2 4 2

2 1 4 2 3

Qeyd

Birinci sorğudan $p_1<p_3<p_4<p_2$ olduğunu öyrəndik.

Beləliklə, axtarılan permütasiya belədir: $[1,4,2,3]$.

Qiymətləndirmə

$q$ — proqramınızın istifadə edə biləcəyi maksimum sorğu sayıdır.

1. ($3$ bal) $n\le 16,q=256,t=128$

2. ($7$ bal) $n\le 32,q=256,t=128$

3. ($8$ bal) $n\le 256,q=256,t=128$

4. ($14$ bal) $n\le 512,q=256,t=128$

5. ($20$ bal) $n\le 512,q=128,t=256$

6. (maksimum $48$ bal) $n\le 1024,q=127,t=256$; $k$ — bir verilənlər dəstində istifadə etdiyiniz maksimum sorğu sayıdır. Bu test üçün nəticə belə olacaq:

• $0$ bal, əgər $k>127$;

• $48-\lceil \frac{24(k-55)}{37}\rceil$ bal, əgər $55<k\le 127$;

• $48$ bal, əgər $k\le 55$;