(Жеті жай сандар)
Артем би жарысына қатысады. Би орындалғаннан кейін 7 қазылар алқасының әрқайсысы оң ұпай қояды. Осы ұпайлардың қосындысы жалпы ұпай болады. Артем би орындауын жақсы деп санайды, егер оның жалпы ұпайы $N$-ге тең болса. Ол би орындауын тамаша деп санайды, егер би орындау жақсы болса, және әр қазылар алқасының ұпайы жай сан болса. Берілген бүтін $N$ санына қазылар алқасының тамаша би орындауының ұпайлар мысалын шығарыңыз немесе ``-1'', егер ондай ұпайларды қою мүмкін емес болса. Егер есептің бірнеше шешімі болса, кез келгенін шығарыңыз. Енгізу файлының бірінші жолында бір оң бүтін сан $N$ ($5 \le N \le 10^{15}$) беріледі. Егер есептің жауабы болса, бос орынмен бөлінген жеті жай сандарды шығарыңыз. Егер есептің жауабы жоқ болса, ``-1'' шығарыңыз. Вход

5

Ответ

-1

Вход

14

Ответ

2 2 2 2 2 2 2

1-ші есеп бөлімі — 17 ұпай ($1 \le N \le 30$) 2-ші есеп бөлімі — 19 ұпай ($1 \le N \le 1000$) 3-ші есеп бөлімі — 23 ұпай ($1 \le N \le 10^{9}$) 4-ші есеп бөлімі — 41 ұпай ($1 \le N \le 10^{15}$)

(Мансұр Александрды жеңеді)
Үйме тастармен ойын берілген. Ойыншының жүрісі келесі бола алады: бір үймеден еркін сан тас алу, немесе бар үймелерден бірдей сан тас алу. Ойыншылар жүрістерін кезек-кезек жасайды. Жүріс жасай алмайтын ойыншы жеңіледі. Мансұр бұл ойынды Александрмен ойнайды. Үстелдің үстінде екі үйме тастар жатыр, бірінші үймеде $a$, екінші үймеде $b$ тас бар. Бірінші болып Мансұр жүреді. Мансұр ойынға қарап түсінді, егер ол ойында ұтылып қала алса, ол өз жүрісімен үстелге тағы бір үйме тастар қосып кепілді ұта алады. Егер Мансұр үшінші үйме қосса, жүріс Александрға көшеді және содан кейін ойын тек үш үймемемен ойналады. Енді Мансұрдың алдында келесі сұрақ тұр, ол берілген ойынды ұта ала ма, не оған бірінші жүрісімен үстелге тағы бір үйме тастар салу керек па? Егер салу керек болса үймеде қанша тас болу керек? Мансұрға көмек беріңіз. Мансұр мен Александр тәжірибиелі ACM қатысушылары, сондықтан олар әрдайым тиімді түрде жүрістер жасайды. Берілгеннің бірінші жолында бір сан бүтін сан берілген $1 \le T \le 100000$ — тесттердің саны. Келесі $T$ жолдарда тесттер берілген: екі бүтін сан $a$ және $b$, бір бос орынмен бөлінген. $T$ жол шығарыңыз, ``MANSUR''\ егер Мансұр берілген ойында жеңе алса, немесе $x$ санын, егер Мансұрға жеңу үшін $x$ тастан тұратын үйме қосу керек болса. Егер бірнеше жауап болса, кез келгені дұрыс болып саналады. Вход

5
1 1
1 2
3 3
3 5
9 24

Ответ

MANSUR
3
MANSUR
6
MANSUR

1-ші есеп бөлімі — 21 ұпай $1 \le a,b \le 100$ 2-ші есеп бөлімі — 23 ұпай $1 \le a,b \le 10000$ 3-ші есеп бөлімі — 27 ұпай $1 \le a,b \le 1000000$ 4-ші есеп бөлімі — 29 ұпай $1 \le a,b \le 10000000$

(Ең үлкен шаршы)
Сізге $N \times M$ нөл және бір цифрларынан тұратын кесте берілген. Берілген кестеден, қабырғаларында тек бір цифры жазылған ең үлкен шаршыны табыңыз. Енгізу файлының бірінші жолында екі бүтін сан $N$ және $M$ берілген. Келесі $N$ жолдың әрқайсысында $M$ нөл және бір цифрлары берілген. Кестедегі қабырғаларында тек бір цифры жазылған ең үлкен шаршының қабырғасының ұзындығын шығарыңыз. Егер кестеде ондай шаршылар кездеспесе, 0 санын шығарыңыз. Вход

4 5
01111
01011
11001
11111

Ответ

4

Вход

2 3
000
000

Ответ

0

Вход

3 3
011
011
010

Ответ

2

1ші есеп бөлімі — 30 ұпай ($1 \le N, M \le 100$) 2ші есеп бөлімі — 29 ұпай ($1 \le N, M \le 300$) 1ші есеп бөлімі — 41 ұпай ($1 \le N, M \le 1500$)

(XOR-ға тағы бір есеп)
Сізге $n$ бүтін саннан тұратын $A$ сандар реті берілген. Берілген $X$ саны бойынша келесі шарт орындалатын $1 \le l \le r \le n$ қос сандардың санын табыңыз: $X \le A[l]\ xor\ A[l + 1]\ xor\ ...\ xor\ A[r]$. $xor$ - әр бит(екілі сан жүйесінде) тәуелсіз екі сан модулі бойынша қосуы. Сол екі биттің қосындысы операндтардың биттері әртүрлі болғанда бір болады. Мысалы: $10_{10}\ xor\ 23_{10}\ =\ 29_{10}$, $1010_2\ xor\ 10111_2\ =\ 11101_2$. Бұл жерде бір теңдеу екі рет жазылған. Бірінші рет ондық сан жүйесінде, екінші рет екілік сан жүйесінде. Берілгеннің бірінші жолында екі бүтін сан берілген, $n$ және $0 \le X \le 10^9$. Келесі жолда $n$ бүтін теріс емес сандар беілген. Бұл сандар $10^9$-ға дейін. Бір сан, есептің жауабы. Вход

5 0
1 2 3 4 5

Ответ

15

Вход

3 3
1 2 3

Ответ

2

1ші есеп бөлімі, 31 ұпай $1 \le n \le 1000$ 2ші есеп бөлімі, 69 ұпай $1 \le n \le 100000$

(Әдемі кестедегі қосынды)
Сізге $n$ жолдан және $m$ қатардан тұратын кесте $A$ берілген. Бұл кестенің $n \times m$ торлары натуралды сандармен жоғарыдан төменге, солдан оңға қарай белгіленген. $A[i][j]$ деп $i$-жолында және $j$-қатарында тұрған торды белгілейміз. Берілген $x$ саны үшін біздің кесте әдемі болады, егер әр торда $x$ санының дәрежелері жазылған болса. Формалды түрде $A[i][j] = x^{(i - 1) * m + j}$. $q$ сұрау $x1,x2,y1,y2$ берілген кестенің ішіндегі кестенің шектері және $p$ модулі. Әр сұраудың жауабы сол кестенің ішіндегі сандардың қосындысы. Формалды түрде $\left(\sum\limits_{i=x1}^{x2}{\sum\limits_{j=y1}^{y2}{A[i][j]}}\right) mod\ p$. Сұрауларға жауап беретін программа жазыңыз. $3$ жолдан және $4$ қатардан тұратын, $x$ санының әдемі кестесі:\\ $A = \begin{pmatrix} x^{1} & x^{2} & x^{3} & x^{4}\\ x^{5} & x^{6} & x^{7} & x^{8}\\ x^{9} & x^{10} & x^{11} & x^{12} \end{pmatrix}$ Енгізу файлының бірінші жолында үш сан $n,m,x$ берілген. Келесі жолда тек бір сан $q$ берілген. Келесі $q$ жолда сұраулар берілген, әр сұрау бес саннан тұрады $x1,x2,y1,y2,p$, $1 \le x1 \le x2 \le n$, $1 \le y1 \le y2 \le m$. $q$ жол, сұраулардың жауаптарын шығарыңыз. Вход

1 10 2
5
1 1 1 1 1000000007
1 1 1 2 1000000007
1 1 1 5 1000000007
1 1 2 4 1000000007
1 1 2 3 1000000007

Ответ

2
6
62
28
12

1ші есеп бөлімі — 7 ұпай $n = 1$, $1 \le m \le 10$, $1 \le x \le 5$, $1 \le q \le 100$, $p = 10^9 + 7$ 2ші есеп бөлімі — 9 ұпай $1 \le n \le 100$, $1 \le m \le 100$, $1 \le x \le 10^9$, $1 \le q \le 100$, $p = 10^9 + 7$ 3ші есеп бөлімі — 11 ұпай $1 \le n \le 1000$, $1 \le m \le 1000$, $1 \le x \le 10^9$, $1 \le q \le 10^4$, $p = 10^9 + 7$ 4ші есеп бөлімі — 21 ұпай $1 \le n \le 10^9$, $1 \le m \le 10^9$, $1 \le x \le 10^9$, $1 \le q \le 10^4$, $p = 10^9 + 7$ 5ші есеп бөлімі — 52 ұпай $1 \le n \le 10^9$, $1 \le m \le 10^9$, $1 \le x \le 10^9$, $1 \le q \le 10^4$, $1 \le p \le 10^9$

(Информатик қуанышы)
Бұл жылы информатика пәнінің олимпиадасына $N$ оқушы қатысады. Қатысушылар $1$-ден $N$-ге дейінгі сандармен нөмірленген. Жаңа жүйемен, оқушылар есептің шешімін жібергеннен кейін өз ұпайларын лезде көреді. Тексерудің нәтижесінде қатысушының көңіл-күйі қатты өзгеруі мүмкін. Олимпиаданың ең басында барлық қатысушылардың көңіл-күйі бірге тең. Қатысушылардың көңіл-күйі өзгерісі тарихы бар. Қазылар алқасы қатысушылардың көңіл-күйін бақылағысы келеді және сізден көмек сұрайды. Сізде үш түрлі сұрау бар: $0$ $L$ $R$ $P$ - Қазылар алқасы $L$-ден $R$-ге дейін нөмірленген барлық қатысушылардың көңіл-күйінің көбейтіндісін білгісі келеді. Бұл сан өте үлкен болуы мүмкін, сондықтан оны $P$ санының модулімен шығарыңыз. $1$ $L$ $R$ $X$ - $L$-ден $R$-ге дейін нөмірленген барлық қатысушылар тексерудің нәтижесін біліп, әрқайсысы $X$ санына көбейтілді. $2$ $L$ $R$ $X$ - $L$-ден $R$-ге дейін нөмірленген барлық қатысушылар тексерудің нәтижесін біліп, әрқайсысы $X$ санына бөлінді. Бұл бөлікте барлық қатысушылардың көңіл-күйі $X$ санына бөлінетіне кепіл беріледі. Әр сұрауда $1 \le L \le R \le N$. Бірінші жолда екі сан $N$ және $M$, қатысушылар саны және сұраулар саны енгізіледі. Келесі $M$ жолдарда сұраулар беріледі. Әр 0 типті сұрауға, бөлек жолда жауап шығарыңыз. Вход

5 5
0 1 5 1000000007
1 2 3 6
0 1 5 1000000007
2 2 3 3
0 1 5 1000000007

Ответ

1
36
4

Вход

3 5
1 1 3 100
0 1 2 10
2 1 3 100
1 2 3 4
0 1 3 10

Ответ

0
6

Тесттердің 10\%-да, $1 \le X \le 100$, $P = 10^9+7$, $1 \le N \le 5000$, $1 \le M \le 5000$, екінші типті сұраулар жоқ ($x$-ке бөлу) Тесттердің 45\%-да, $1 \le X \le 100$, $P = 10^9+7$, $1 \le N \le 5000$, $1 \le M \le 5000$ Тесттердің 100\%-да, $1 \le X \le 100$, $1 \le P \le 10^9$, $1 \le N \le 50000$, $1 \le M \le 50000$