BS-M6. Ro‘yxatda bormi?

Kutubxonada kitoblar inventar raqami bo‘yicha saralab qo‘yilgan. O‘quvchilar q marta so‘raydi: «x raqamli kitob bormi?» Har so‘rovga YES yoki NO deb javob bering.

Har so‘rovda butun ro‘yxatni ko‘rib chiqish q · n = 4·10¹⁰ amal — ulgurmaydi. Ro‘yxat saralangan: o‘rtadagi kitobga qarab, qidirish oralig‘ining yarmini tashlab yuborish mumkin.

Kirish ma’lumotlari

Birinchi qatorda n, ikkinchisida o‘sish tartibida (kamaymaydigan) n ta butun son. Uchinchi qatorda q, to‘rtinchisida q ta so‘rov — butun sonlar x.

Chiqish ma’lumotlari

Har so‘rovga alohida qatorda YES yoki NO.

Cheklovlar

1 ≤ n, q ≤ 2·10⁵; sonlar modul bo‘yicha 10⁹ dan oshmaydi.