All Tracks Basic Programming Bit Manipulation Basics of Bit Manipulation Problem

( Problem B ) Pikachu vs Team Meowstic and Helping Hand
Tag(s):

Basic Programming, Basics of bit manipulation, Bit Manipulation, Easy

Problem
Editorial
Analytics

Pikachu loves battling with other Pokemon. This time he has a team of $$ N $$ Meowstic to fight, $$i^{th}$$ of which has strength $$ a_i $$. He wants to fight with all of them $$K $$ times. Team Meowstic came to know about this and now they have devised a strategy to battle against the mighty Pikachu.

All the $$N$$ Meowstic stand in a straight line numbered from $$1$$ to $$N$$. Before every round of battle, they simultaneously use a move, called Helping Hand. It changes the attacking power of Team Meowstic as follows:

  • The attacking power of first Meowstic remains $$ a_1 $$.
  • The attacking power of remaining Meowstic changes as $$ a_i = a_i | a_{i-1} $$ where $$ 2 \le i \le N $$ and $$ A | B $$ represents the bitwise OR of $$ A $$ and $$ B $$ 

For example, if the current attacking powers are $$ [2, 1, 4, 6, 3] $$, after using the Helping Hand, the powers change to $$ [2, 1|2, 4|1, 6|4, 3|6] $$, or $$ [2, 3, 5, 6, 7] $$.

Help Pikachu by finding the attacking powers of all Meowstic when he fights each of them for the last time, that is, for the $$K^{th}$$ round.

Note that, the influence of Helping Hand remains forever, and attacking powers DO NOT revert back after any round.

Constraints:

  • \(1\le N\le 10^5\)
  • \(0\le K\le 10^9\)
  • \(0\le a_i < 2^{30}\)

Input format:

  • First line contains two space separated integers, $$ N $$ and $$ K $$
  • Second line contains  $$ N $$ space separated integers, the $$ i^{th} $$ of which is $$ a_i $$ 

Output format:

  • Output a single line containing $$ N $$ integers, the $$ i^{th} $$ of which is $$ a_i $$ after the last round 
SAMPLE INPUT
5 3
1 2 3 4 5
SAMPLE OUTPUT
1 3 3 7 7
Explanation

Battle 1:

 $$ a_1 = 1, a_2 = 1 | 2 = 3, a_3 = 2 | 3 = 3, a_4 = 3 | 4 = 7, a_5 = 4 | 5 = 5 $$

Battle 2:

$$ a_1 = 1, a_2 = 1 | 3 = 3, a_3 = 3 | 3 = 3, a_4 = 3 | 7 = 7, a_5 = 7 | 5 = 7 $$

Battle 3:

$$ a_1 = 1, a_2 = 1 | 3 = 3, a_3 = 3 | 3 = 3, a_4 = 3 | 7 = 7, a_5 = 7 | 7 = 7 $$ 

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Easy '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?