Bit operations

Plus

Problem description Progress

ID 34956. Binary strings of given length

Given number N print all strings of length N consisting of zeros and ones in lexicographic order.

In solving the problem, use enumeration of all subpatterns.

Input

Single number N is given. (natural, 1 ≤ N ≤ 10)

Output

It is necessary to print all strings of length N consisting of zeros and ones in lexicographic order, one per line

Input	Output
2	00 01 10 11

ID 34957. Binary strings of given length in reverse order

Темы: Bit operations

Given number N print all strings of length N consisting of zeros and ones in reverse lexicographical order.

In solving the problem, use enumeration of all subpatterns.

Input

Single number N specified. (1 ≤ N ≤ 10)

Output

It is necessary to output all strings of length N consisting of zeros and ones in reverse lexicographical order.

Input	Output
2	eleven 10 01 00

ID 29641. Quiet Don №1

Темы: Bit operations

In peacetime, the Cossacks are engaged in agriculture. Pantelei Prokofievich Melekhov grows special mathematical vegetables that grow according to very strange rules: each seed i of these vegetables has a yield value ai, and the yield of the entire garden bed is the product of the yields of all the seeds planted on it. Melekhov has N seeds. Help him choose a few of these seeds so that when planting these seeds, the yield of the garden bed is maximum.

Input:

The first line contains the number N (1 <= N <= 15)

Second - N numbers ai, possibly real (|ai| < 10)

Output:

Output the maximum yield of the bed, to at least 6 decimal places, that can be achieved with the given set of seeds. It is guaranteed that it is greater than 1.

Input	Output
5 2.0 -1.2 4.7 -2.9 -1.1	32.712000

(с) Grigoriev E., 2018

ID 38513. Equations of Mathematical Magic

Темы: Case Study Bit operations

Colossal! — exclaimed the hunchback. — Programmer! We need a programmer.
Arkady and Boris Strugatsky, Monday starts on Saturday
Studying the book "Equations of Mathematical Magic" Roman Oira-Oira and Cristobal Junta discovered an interesting equation: a−(a⊕x)−x=0 for a given a, where ⊕ stands for bitwise exclusive OR (XOR) of two numbers (this operation is denoted as ^ or xor in many modern programming languages). Since this equation was intended to be solved on the Aldan-3 machine, all calculations were performed on non-negative integers modulo 2³². Oira-Oira quickly found x, which is a solution, but Cristobal Junta found Oira-Oira's result not interesting enough, so he asked a colleague how many solutions there are to this equation. Since all calculations are done modulo 2³², Cristobal Junto is interested in the number of solutions x such that 0 ≤ x≤ 2³². Such a task turned out to be too difficult for Oira-Oira, so he turned to you for help.

Input
The first line contains a single integer a (0 ≤ a ≤ 2³²−1).

Imprint
Print a single integer — the number of non-negative solutions of the equation.

Note
Let's define the bitwise OR (XOR) operation. Let two non-negative integers x and y be given, consider their binary representations (possibly with leading zeros): x_k...x₂x₁x₀ and y_k...y₂y₁y₀ . Here x_i is the i-th bit of x and y_i is the i-th bit of y. Let r=x⊕y — the result of an XOR operation on the numbers x and y. Then the binary representation of r is r_k...r₂r₁r₀, where:

\(r_i = \begin{cases} 1, & \quad \text{if } x_i \neq y_i \\ 0 , & \quad \text{if } x_i = y_i \end{cases} \)

In the first example, the solutions to the equation are 0 and 2147483648=2³¹, because 0−(0⊕0)−0=0−0−0=0 and 0−(0⊕ 2147483648)− 2147483648=−4294967296=−2³²=0 modulo 2³².

In the second example, the solutions to the equation are 0, 2, 2147483648=2³¹ and 2147483650=2³¹+2.

In the third example, the solutions are all x for which 0 ≤ x≤ 2³².

Examples

#	Input	Output
1	0	2
2	2	4
3	4294967295	4294967296

ID 39385. XOR World

Темы: Bit operations

Let \(F(A, B) = A \oplus (A+1) \oplus (A+2) \oplus ... \oplus B\) , where \(\oplus\) is the exclusive OR operation (XOR).
Given the known numbers A and B calculate F(A, B).

Input
The input is a string containing 2 numbers: A and B (0 <= A, B <= 10¹²).

Imprint
Output F(A, B).

Examples

#	Input	Output
1	2 4	5
2	123 456	435
3	123456789012 123456789012	123456789012

ID 44386. And Ka

Темы: Bit operations

Gromozeka studies bit operations. Today he will learn the bitwise AND operation (&). Now he was wondering what is the largest integer value of k that will satisfy the condition written below.

x & (x - 1) & (x - 2) & ... & k = 0

Input
The first line of the input contains an integer t (1 <= t <= 3*10⁴) - the number of integers x for which you want to find the answer. Next, the program receives t lines, each of which contains one integer x (1<= x <= 10< sup>9).

Imprint
For each x value, on a separate line print the largest integer k value that will satisfy the problem condition.

Examples

#	Input	Output
1	3 2 5 17	1 3 15

ID 44387. XOR hash

Темы: Bit operations

Gromozeka has n-1 integers written on cards and laid out in a row in random order. It computed a bitwise XOR (xor) between all the numbers written. The calculated number (X) he wrote down on a new card and added it to the end of all cards with numbers. Now he has n number cards. He shuffled all the cards and arranged them again in a row in random order.

Gromozeka showed you all the n cards and asks you to guess the number X that was written on the new card.

Input
The first line of the input contains an integer n - the number of cards with numbers (2 <= n <= 100). The second line contains n integers - the numbers written on the cards (each number belongs to the interval [0, 127]).

Imprint
Print the answer one integer - the number X that was written on the new card.
It is guaranteed that the answer exists. If there are multiple answers, print the minimum X.

Examples

#	Input	Output
1	4 4 3 2 5	2

ID 44389. Wizard ORZ

Темы: Bit operations

The ORZ Wizard loves to conjure numbers. You decided to test its strength and gave it an array a consisting of n integers, as well as an integer z. The numbering of array elements starts from 1.

The ORZ wizard performs the following operation any number (possibly zero) times:

It selects an integer i such that 1<= i <= n. Then he whispers a spell and after that at the same time the number a_i turns into a number equal to (a _i or z), and the number z turns into a number equal to (a_{i and z}).

Here or and and denote the bitwise OR and bitwise AND operations, respectively.

Find the maximum possible value of the maximum element in the array a after some (possibly zero) number of transformations.

Input
The first line of the input contains two integers: n and z (1 <= n <= 2000, 0 <= z < 2³⁰). The second line of the input contains n integers: a₁, a₂,...,a_n (0 <=

a_i<2³⁰). It is guaranteed that the sum of n  values over all test cases does not exceed 10⁴.



Imprint

Print the answer to the problem.

 

 
Examples




#
Input
Output
Note




1
2 3

3 4
7

One of the optimal sequences of actions is the following:


Perform operation on i = 1. Now a1 becomes (3 or 3) = 3 and z becomes (3 and 3) = 3. 
Perform operation for i = 2. Now a2 becomes (4 or 3) = 7, and z becomes equal to (3 and 3) = 0.
Perform operation on i = 1. Now a1 becomes (3 or 0) = 3 and z becomes (3 and 0) = 0.


After these operations, the sequence a becomes equal to [3,7], and the maximum value in it is equal to 7. It can be proved that the maximum value in a cannot exceed 7 in any sequence of operations, so the answer is 7.



2
5 5

0 2 4 6 8
13

ID 44507. Max XOR - 2

Темы: Bit operations

Two numbers a and b are written in hexadecimal notation. Both entries are of length n. You can swap two adjacent digits as many times as you like in any of the numbers. What is the maximum value the result of applying the bitwise operation XOR to the numbers obtained after applying such permutations?

This operation is defined on the binary representation of numbers.

Let's define the bitwise XOR operation (XOR). Let two integer non-negative binary numbers x and y of length k (possibly with leading zeros) be given: < code>x_k-1...x₂x₁x₀and y_k-1...y₂y₁y₀. Here x_i is ith bit of x and y _i is the ith bit of y. Let r = x XOR y - result of XOR operation on numbers x and y< /code>. Then the binary notation r will be r_k-1...r₂r₁r₀, where:



\(r_i = \begin{cases} 1, ~ \text{if} ~ x_i ~ \neq ~ y_i \\ 0 , ~ \text{if} ~ x_i ~ = ~ y_i \end{cases}\)




Input

The first line contains a single integer n (1 <= n <= 100000) - the length of the numbers. The second line contains the number entry a. The third line contains the number b.

The letters A, B, C, D, E, F represent the numbers 10, 11, 12,  ;13, 14, 15 in hexadecimal, respectively. Entries can contain leading zeros.


Output

In a single line, you need to print one hexadecimal number of length n, which is the answer to the question from the condition.


Note

In the first example, you can swap two adjacent digits in the first number, you get F0 XOR 0E = FE.

In the second example, any permutation of the digits does not change a  XOR  b. Please note that the length of the output number must be equal to  n, so you must print leading zeros.

In the third example, you can get 101010 from a and 010100 from b. 
 

Examples




#
Input
Output




1

2
0F
0E


FE



2

3
000
000


000



3

6
010110
011000


111110

ID 34915. 2^n+2^m

Темы: Bit operations

Find the sum of two different powers of 2 using only bitwise operations. In particular, you cannot use the addition operation.

Input: Two unequal numbers are given: n and m, not exceeding 31.
Output: Display the value of the sum 2ⁿ+2^m.< br />
Examples

#	Input	Output
1	1 2	6

ID 44570. 2^k

Темы: Bit operations

Write a program that, given a number k (0 <= k <= 31), displays the number 2^k , that is, a number whose k-th bit is 1, and the rest are zeros.

Arithmetic operations cannot be used in the program, only bit operations must be used!

Examples

#	Input	Output
1	5	32

ID 44571. Minimum OR amount

Темы: Bit operations

Gromozeka wrote down n numbers on a piece of paper a_i. It then performs the following operation on the array

selects two distinct integers i, j (1 <= i < j <= n) and ;replaces a_i to x and a_j to y. In order not to break the array, Gromozeka should make sure a_i|a_j=x|y, where |< /code> denotes bitwise OR. Note that x and y are non-negative integers.



Gromoseka wants to determine the minimum sum of array elements that he can get after performing the above operation any number of times. Since Gromozeka needs to go on his next space journey as soon as possible, he asks for your help!


Input

The  first line of the  input contains an integer n (2 <= n <= 100) -  nbsp;nbsp;nbsp;nbsp; leaf. The second line of the input contains n integers a₁,a₂,…,a_n (0<=a_i<= 2³⁰).


Output

Print the minimum possible sum of the array.





Examples




#
Input
Output




1

3
1 3 2


3




2

5
1 2 4 8 16


31



3

2
6 6


6



4

3
3 5 6


7

ID 44572. Set the beat

Темы: Bit operations

Write a program that sets 1 to the kth bit of the N. Display the resulting number.

Arithmetic operations cannot be used in the program, only bit operations must be used!

Input

Given an integer N and a natural number k.

Output

Display the number obtained after setting the given bit to 1.

Examples

#	Input	Output
1	5 1	7

ID 44573. Invert the bit

Темы: Bit operations

Write a program that inverts the kth bit of a N. Display the resulting number.

Arithmetic operations cannot be used in the program, only bit operations must be used!

Input

Given an integer N and a natural number k.

Output

Display the number obtained after inverting the given bit.

Examples

#	Input	Output
1	5 2	1

ID 44574. Reset the beat

Темы: Bit operations

Write a program that resets (sets to 0) the kth bit of a N. Display the resulting number.

Arithmetic operations cannot be used in the program, only bit operations must be used!

Input

Given an integer N and a natural number k.

Output

Display the number obtained after resetting the given bit.

Examples

#	Input	Output
1	5 2	1

ID 44575. Reset all beats except the last

Темы: Bit operations

Write a program that resets (sets to 0) all bits of N except the last k bits. Display the resulting number.

Arithmetic operations cannot be used in the program, only bit operations must be used!

Input

Given an integer N and a natural number k.

Output

Display the number obtained after the bits have been reset.

Examples

#	Input	Output
1	5 1	1

ID 44576. Determine the value of a bit

Темы: Bit operations

Write a program that determines the k-th bit of N.

Arithmetic operations cannot be used in the program, only bit operations must be used!

Input

Given an integer N and a natural number k.

Output

Display the value of the given bit (0 or 1).

Examples

#	Input	Output
1	5 1	0

ID 44577. Byte bit by bit

Темы: Bit operations

Write a program that prints out all the bits of an 8-bit number N.

Input

Given an integer N (0 <= N <= 255).

Output

Print a number N in bit form: 8 bits, high bits on the left, low bits – right.

Examples

#	Input	Output
1	5	00000101

ID 44578. Fast multiplication

Темы: Bit operations

Numbers a and b are given. Without using the operations *, /, //, % calculate them work.

Input

Given two numbers a and b.

Output

Print the product of numbers a and b.

Examples

#	Input	Output
1	5 2	10

ID 44579. Set low bit to zero

Темы: Bit operations

Given a number, replace the low zero bit (first zero from the right) by one.

Branches and loops are prohibited.

Input

The program receives a non-negative number a.

Output

Print the resulting number.

Examples

#	Input	Output
1	0	1
2	5	7

ID 44580. Reset low unit

Темы: Bit operations

Given a number, reset the lower non-zero bit (i.e. replace the first one from the right to zero).

Branches and loops are prohibited.

Input

A single non-negative number a.

Output

Print the resulting number.

Examples

#	Input	Output
1	1	0
2	5	4

ID 44583. Max XOR

Темы: Bit operations

The two numbers a and b are written in binary. Both entries are of length 2n. Both entries are divided into n blocks of 2 adjacent numbers. In each of the numbers, you can swap two arbitrary blocks as many times as you like. What is the maximum value the result of applying the bitwise XOR operation to the resulting numbers can have?



\(r_i = \begin{cases} 1, ~ \text{if} ~ x_i ~ \neq ~ y_i \\ 0 , ~ \text{if} ~ x_i ~ = ~ y_i \end{cases}\)




Input

The first line contains a single integer n (1 <= n <= 100000) - number of blocks of two digits in both numbers. The second line contains the number entry a. The third line contains the number b.

For convenience, the blocks are separated by the symbol "|".


Output

In a single line, you need to print one binary number from n blocks, which is the answer to the problem, in the same block format as the given numbers a and b.


Note

In the first example, you can swap two adjacent blocks in the first number, you get 11|00  XOR  00|10=11|10.

In the second example, any permutation of digits does not change a  XOR  b. Please note that the length of the output number must consist of n blocks, so you must print blocks of leading zeros.

In the third example, you can get 101001 from a and 010100 from b.

 

Examples




#
Input
Output




1

2
00|11
00|10


11|10



2

3
00|00|00
00|00|00


00|00|00



3

3
10|10|01
00|01|01


11|11|01