## WC '17 Finals J1 - Cownterintelligence

View as PDF

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type
##### Woburn Challenge 2017-18 Finals Round - Junior Division

The Great Cow-Monkey War of 2017 has left Scarberia in a fragile and unstable state. Interspecies tension is at an all-time high, and both sides are working relentlessly to rebuild their economies, social systems, and militias. Little do the cows and monkeys know that, amidst the turmoil, the world is at risk of being taken over by an even more dangerous foe — a group of aliens known as the Party of Extraterrestrial Gangsters (or PEG for short)! PEG has decided that it's the perfect time to divide and conquer Scarberia by exploiting its current internal hostilities.

Prior to their invasion, PEG would like to obtain some intel on the military of each group, starting with the cows. The entire cow army consists of soldiers numbered from 1 to . PEG has sent spies to infiltrate the cow army. Each of the spies has chosen a distinct cow soldier to abduct and steal the identity of. In other words, of the cow soldiers are now secretly imposters.

The commander of the cow army, Bo Vine, is a sharp leader. Recently, he has sensed something amiss with his subordinates and would like to find out if his army has been compromised. Being one of the greatest military strategists of our time, he had long planned for the day that something like this might happen. During the inception of the cow army, a secret system to identify spies was established. This system is based on the fact that all real cows have perfect pitch, and can moo at any musical frequency at will. In the past, Bo Vine had chosen a single secret musical note to share with every cow soldier on the first day of basic training. The fundamental frequency of the secret note to moo is Hz, where is an integer. When questioned, they must moo this note or be revealed as a spy.

Bo Vine has questioned all of the cows individually and gathered some data. He has recorded that the cow numbered moos at a frequency of Hz, where is an integer. However, upon inspecting the data, Bo Vine has noticed a big problem with his plan. He realized that he had only told the name of the secret note to the cows, and not its exact frequency. He forgot that the same musical note can be mooed in different octaves, and hence may have different frequencies. Thus, each real cow soldier could have mooed the secret note at frequency , or at some higher octave with a frequency larger than the fundamental frequency .

To give you a little background in music theory, pitches that are octaves above a given fundamental pitch will have frequencies x, x, x, and all other powers of two times the fundamental frequency. For example, if Bo Vine chose the secret note to be A at Hz as the fundamental frequency, then any cows mooing at frequencies Hz, Hz, Hz, Hz, etc. should be deemed to be real cow soldiers. Any other frequency is indicative of an imposter! Given the fundamental frequency and the moo frequency of every cow soldier, please help Bo Vine identify which of them are actually alien imposters.

In test cases worth of the points, and for each .

#### Input Specification

The first line of input consists of two space-separated integers, and .
lines follow, the -th of which consists of a single integer, , for .

#### Output Specification

Output lines with a single integer per line, the numbers of all of the cows that are deemed to be imposters. You should output these numbers in ascending order.

#### Sample Input

6 440
880
500
3520
441
1320
440

#### Sample Output

2
4
5

#### Sample Explanation

There are cow soldiers. Cows numbered , , and mooed at frequencies Hz, Hz, and Hz respectively, which are not power-of-2 multiples above the fundamental frequency of Hz.