In Minecraft, potions can be made and drank. When drank, they apply the corresponding potion effect to the player for some specified amount of time. “A Furious Cocktail” is the name of the advancement where a player has every potion effect applied at the same time.

This is a challenging feat, as it takes time to drink each potion, and only one potion can be drank at a time. Suppose that in your inventory, there are N unique potions that have a time duration of t1,,tN seconds, respectively. Assuming that it takes T seconds to drink a potion, is it possible to have all N potion effects applied at the same time?

Note that if one potion’s effect ends at the same time you finish drinking another potion, the potions are not considered to be applied at the same time.

Input

The first line consists of 2 integers, 0