More Counterfeit Masses

Alright, as promised, I should post the harder version of the counterfeit masses problem now. I first learned this problem from Jen:

You have a balance scale and 40 coins. 39 of the coins are identical while the other one is a counterfeit. The only difference with a counterfeit coin is that it has a slightly different weight than other coins. You may only use the balance scale to make 4 measurements, find an algorithm that is guaranteed to identify the counterfeit coin.

The main difference here is that you do not know if the counterfeit coin is heavier or lighter, so when you make a measurement you only learn that the counterfeit coin is either "on the left and heavier" or "on the right and lighter", or things like that.

Of course, the rules for the balance scale are the same as for the original problem.