Niech N będzie zadaną n-cyfrową liczbą naturalną zapisaną w systemie pozycyjnym o podstawie d. Znajdź możliwie najdokładniejsze przybliżenie dolne liczby N w zapisie zmiennopozycyjnym, gdzie mantysa i cecha są liczbami całkowitymi zapisanymi w systemie o podstawie 2, w notacji uzupełnień do 2, długości odpowiednio m oraz c. W przypadku niejednoznaczności rozwiązania, wskaż przybliżenie liczby N o największej wartości mantysy (tzw. postać znormalizowana).

Uwaga! Przybliżenie dolne liczby x to liczba y, której wartość bezwzględna jest mniejsza bądź równa wartości bezwzględnej liczby x.



WEJŚCIE

Wiersz zawierający liczby n, d, m oraz c oddzielone znakami odstępu (kod ASCII 32) zakończony znakiem nowej linii (kod ASCII 10). Następnie wiersz opisujący liczbę N jako ciąg kolejnych wartości pozycyjnych tejże liczby (od najbardziej do najmniej znaczących) zapisanych za pomocą stosownych liczb z zakresu od 0 do d-1. Elementy w/w ciągu oddzielone są znakami odstępu, ciąg zakończony jest znakiem nowej linii.



WYJŚCIE

Dwa wiersze, z których każdy zakończony jest znakiem nowej linii, reprezentujące postać binarną odpowiednio:

 - poszukiwanej mantysy,

 - poszukiwanej cechy,

w kolejności od najbardziej do najmniej znaczących bitów.

Dodatkowo: wiersz zawierający liczbę kontrolną równą liczbie znaków właściwych wczytanych z wejścia (znak właściwy to każdy znak niebędący znakiem białym, tj. znak odstępu, znak nowej linii, znak tabulacji, oraz znakiem końca pliku, tj. EOF).



OGRANICZENIA

Długość n liczby i podstawa systemu pozycyjnego d zawarte w przedziałach stosownie [1,10^7] oraz [3,10^9]. Długość m mantysy i c cechy ograniczone przez 2 i 10^3.



PRZYKŁAD 1

wejście:

3 3 5 3


2 1 0

wyjście:

01010


001



/* KOMENTARZ DO ROZWIĄZANIA


Parametry zadania:


n=3 (długość liczby N),


d=3 (podstawa systemu pozycyjnego liczby N)


m=5 (długość mantysy),


c=3 (długość cechy).


Liczba N = 2 1 0 zapisana w systemie o podstawie d=3 odpowiada liczbie N(10)= 2*3^2 + 1*3^1 + 0*3^0 = 18 + 3 + 0 = 21 zapisanej w systemie o podstawie 10. Natomiast liczba N(10) odpowiada liczbie N(2) = 1 0 1 0 1 zapisanej w systemie po podstawie 2.


Mantysa poszukiwanej reprezentacji składa się z m=5 cyfr, z czego pierwsza z nich jest zarezerwowana dla stosownej wartości ujemnej w notacji uzupełnień do 2. Stąd mantysa zawiera 4 najbardziej znaczące cyfry liczby N(2) poprzedzone w/w cyfrą wartości ujemnej, tj. 01010.


Możliwie najdokładniejsze przybliżenie dolne liczby N(2) w zapisie zmiennopozycyjnym uzyskamy wymnażając wyznaczoną mantysę 01010 przez 2 (przesuwając o jedną pozycję binarną w lewo). Tym samym poszukiwana c=3 cyfrowa cecha, w notacji uzupełnień do 2, ma postać 001.


Ostatecznie odpowiedź stanowi para ciągów:


01010


001 */



PRZYKŁAD 2

wejście:

5 5 15 10


4 3 2 1 0

wyjście:

010110111001000


1111111110




PRZYKŁAD 3

wejście:

40 20 20 15


19 13 0 18 13 19 15 12 19 3 12 19 2 10 19 14 16 7 1 1 18 5 12 7 5 8 7 19 8 0 16 10 13 1 11 11 7 10 19 9

wyjście:

01110011100000011000


000000010011010