99 Bottles of Beer

Interview

Time limit1sMemory limit512 MB

Summary

Given N, print the full lyrics of the N Bottles of Beer song, with correct singular and plural wording.

Level: Easy2 of 10
Topics: Implementation, String, Simulation, Brute force
Solved: No attempts yet

Problem

The lyrics of the song 99 Bottles of Beer are often used as a programming exercise, much like Hello World. Our goal is to sing N Bottles of Beer. A high school student drinking beer would not fit the law-abiding spirit of Sunrin students who spread their dreams to the world and the future, but since we are not actually drinking beer and only singing the song, it does not matter.

The lyrics of N Bottles of Beer are produced by the following process. Suppose there are currently K bottles of beer on the wall. Initially K = N. Then, while taking down one bottle of beer, print the following.

K bottles of beer on the wall, K bottles of beer.
Take one down and pass it around, K-1 bottles of beer on the wall.

However, to express that there is only one bottle of beer, you must write 1 bottle, not 1 bottles. Also, to express that there are no bottles of beer, you must write no more bottles, not 0 bottles.

If beer still remains, repeat the process above; if no beer remains, print the following and terminate. Likewise, when buying just one bottle of beer, you must write 1 bottle, not 1 bottles.

No more bottles of beer on the wall, no more bottles of beer.
Go to the store and buy some more, N bottles of beer on the wall.

Input

A natural number N between 1 and 99 inclusive is given.

Output

Print the lyrics of N Bottles of Beer.

Examples1

Example 1

Input

Expected output

3 bottles of beer on the wall, 3 bottles of beer.
Take one down and pass it around, 2 bottles of beer on the wall.

2 bottles of beer on the wall, 2 bottles of beer.
Take one down and pass it around, 1 bottle of beer on the wall.

1 bottle of beer on the wall, 1 bottle of beer.
Take one down and pass it around, no more bottles of beer on the wall.

No more bottles of beer on the wall, no more bottles of beer.
Go to the store and buy some more, 3 bottles of beer on the wall.