Школа се састоји од \(n\) учионица распоређених у круг. У неким учионицама налазе се професори који држе час, тако да је у свакој учионици или један или ниједан професор. Професори су познати по томе да их мрзи да много ходају и да умеју да ходају само у смеру казаљке на сату. Након што звоно означи крај часа, сваки професор погледа да ли се у следећој учионици (у смеру казаљке на сату) налази професор који је управо завршио час. Ако се не налази, он ће следећи час одржати у тој следећој учионици, док ако је неког било тамо он одлучује да остане у истој учионици у којој је малопре одржао час, и понови час истим ђацима (јадни они).

На слици је дат пример како се мења распоред професора при преласку из једног школског часа у наредни. Црна поља означавају учионице са професором, бела поља су учионице без професора.

Ако је познат распоред професора по учионицама на првом часу, одредити распоред на \(k\)-том часу.

Опис улаза

У првој линији улаза налазе се природни бројеви \(n\), број учионица у школи, и \(k\), редни број часа за који треба одредити распоред. У другој линији улаза налази се опис учионица на првом часу дат као \(n\) карактера. Учионице су наведене у смеру казаљке на сату, и за сваку учионицу записан је карактер \(1\) ако се у учионици налази професор, односно \(0\) ако се не налази.

Опис излаза

Нека је \(S\) низ од \(n\) елемената који представља стања учионица на \(k\)-том часу. \(S[i] = 0\) ако је \(i\)-та учионица на часу \(k\) празна, односно \(S[i] = 1\) ако је у њој професор.

У једину линију излаза исписати опис учионица на \(k\)-том часу, на следећи начин. Ако је \(n \leq 10^5\), исписати низ \(S\) (без размака). Ако је \(n > 10^5\), исписати \(10^5\) бројева, сваки или \(0\) или \(1\), где \(i\)-ти број представља XOR свих бројева низа \(S\) на позицијама чији је индекс конгруентан са \(i\) по модулу \(10^5\).

Овакав начин исписивања се тражи да би се уштедело време потребно за испис, и не мења суштину задатка. Уколико већ имате израчунат низ \(S\), можете искористити следећи C++ код за испис.

    int M = 100000;
    int l = min(n, M);
    for (int i = 0; i < l; i++) {
        int a = 0;
        for (int j = i; j < n; j += M) {
            a ^= S[j];
        }
        printf("%i", a);
    }

У програмском језику Pascal, под претпоставком да сте декларисали ове променљиве, ~~~ l, i, j, a : Longint; S : array[1..n] of Integer; ~~~ за испис можете користити следећи код. ~~~ l := Min(n, M); for i := 1 to l do begin a := 0; j := i; while (j <= n) do begin a := a xor S[j]; j := j + M; end; Write(a); end; ~~~

Примери

<div class="panel panel-default">
    <div class="panel-heading">
        <span class="pull-left" style="width: 48%;">Ulaz</span>
        <span style="padding-left: 15px;">Izlaz</span>
    </div>
    <div class="panel-body">
        <span class="pull-left exampleinput">
            16 2<br/>
            1011101100110100
        </span>
        <span class="exampleoutput">
            0111011010101010
        </span>
    </div>
</div>

<div class="panel panel-default">
    <div class="panel-heading">
        <span class="pull-left" style="width: 48%;">Ulaz</span>
        <span style="padding-left: 15px;">Izlaz</span>
    </div>
    <div class="panel-body">
        <span class="pull-left exampleinput">
            10 4<br/>
            1110010110
        </span>
        <span class="exampleoutput">
            0101010111
        </span>
    </div>
</div>

Објашњење примера

Први тест пример је приказан на слици у задатку. У другом тест примеру распоред по часовима је:

1. 1110010110
2. 1101001101
3. 1010101011
4. 0101010111

Ограничења

Тест примери су подељени у четири дисјунктне групе: * У тест примерима који вреде 20 поена важиће \(1 \leq n \leq 10^5\) и \(1 \leq k \leq 10^5\). * У тест примерима који вреде 12 поена важиће \(1 \leq n \leq 10^5\) и \(10^5 < k \leq 10^9\). * У тест примерима који вреде 8 поена важиће \(10^5 < n \leq 10^7\), \(1 \leq k \leq 10^5\) и број професора није већи од \(10^5\). * У тест примерима који вреде 60 поена важиће \(10^5 < n \leq 10^7\), \(10^5 < k \leq 10^9\).