Fişierul intrare/ieşire:	sormin.in, sormin.out	Sursă	ad-hoc
Autor		Adăugată de	Cosmin-Mihai Tutunaru •stocarul
Timp execuţie pe test	0.75 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sormin

Se dau un şir A[1..N] şi un număr S.

Cerinţă

Dintre toate subşirurile de suma S, să se determine un subşir pentru care suma OR, pe biţi, este minimă.

Date de intrare

Fişierul de intrare sormin.in conţine pe primul rând numerele N şi S. Pe a doua linie sunt scrise N numere naturale separate prin câte un spaţiu.

Date de ieşire

În fişierul de ieşire sormin.out se vor scrie pe prima linie numerele R şi M, reprezentând suma OR, pe biţi minimă, respectiv numărul de elemente ale subşirului determinat. Pe a doua linie vor fi scrise, separate prin câte un spaţiu cele M elemente ale subşirului determinat.

Restricţii

• 1 ≤ N ≤ 100000
• 1 ≤ S ≤ 50000
• 1 ≤ A[i] ≤ 5000
• Fie x şi y două numere naturale. Pentru fiecare din ele avem câte o reprezentare în baza 2, x[k],x[k-1],…,x [1],x [0] şi respectiv $y[k],y[k-1],…,y [1],y [0]. În cazul în care lungimile reprezentărilor sunt diferite, cea mai scurtă dintre ele se poate prelungi spre stânga cu zerouri. Prin suma OR, pe biţi, a numerelor x şi y se înţelege numărul z cu reprezentarea z[k],z[k-1],…,z [1],z [0] unde z[j] = x[j] | y[j], este operaţia definită prin 0 | 0 = 0, 0 | 1 = 1, 1 | 0 = 1, 1 | 1 = 1, 0 ≤ k. De exemplu x = 12 şi y = 9 au reprezentările binare 1100 şi 1001, iar x | y = 1101 = 13
• Pentru testele date se garantează existenţa unei soluţii
• Dacă există mai multe subşiruri cu suma OR minimă, atunci oricare din ele va fi considerat corect. De asemenea, elementele subsirului pot fi afisate in orice ordine.

Exemplu

Explicaţie

Nu putem obţine suma 20 doar cu elemente egale cu 2. Putem obtine suma 20 folosind elementele egale cu 2 şi 3. Suma OR este 3, deoarece 2 are reprezentarea binara 10, iar 3 are reprezentarea binară 11, deci 2 | 3 = 3

Cum se trimit solutii?