Bittijono |
| Time limit: | 2.00 s |
| Memory limit: | 512 MB |
|
Ääretön bittijono on muodostettu aloittamalla jonosta 0 ja lisäämällä joka vaiheessa jonon perään senhetkinen jono niin, että jokainen bitti on käänteinen.
Bittijono alkaa siis muodostua seuraavasti:
- 0
- 01
- 0110
- 01101001
- 0110100110010110
- 01101001100101101001011001101001
- ...
Tehtäväsi on vastata $n$ kyselyyn koskien bittijonon sisältöä. Jokaisessa kyselyssä sinulle annetaan kokonaisluku $k$ ja sinun tulee ilmoittaa jonon kohdassa $k$ oleva bitti. Bitit on numeroitu alkaen luvusta 1.
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku $n$: kyselyiden määrä.
Sitten syötteessä on $n$ riviä, joista jokaisella on yksi kokonaisluku $k$: kohta bittijonossa.
Tuloste
Tulosta jokaiseen kyselyyn bittijonon kohdassa $k$ oleva bitti.
Esimerkki
Syöte:
3
5
2
7
Tuloste:
1
1
0
Osatehtävä 1 (10 pistettä)
- $1 \le n \le 100$
- $1 \le k \le 100$
Osatehtävä 2 (19 pistettä)
- $1 \le n \le 10^5$
- $1 \le k \le 10^6$
Osatehtävä 3 (71 pistettä)
- $1 \le n \le 10^5$
- $1 \le k \le 10^{18}$
