I was pretty sure google print ads would never work. Electronic media is quickly taking the market, and as the new generation becomes the majority, printed media will fall into some serious problems. Today's 20-30 will soon become the future's 40-50, and we have been raised to read online news channels.
I have no idea what your newspapers look like, but ours are hilarious. Sales have dropped so much, that every single newspaper has 2-3 mini magazines inside on a certain theme, specials, extras, 1-2 movie DVDs. The Sunday editions literally weigh over a kilogram.
The only ones still making serious numbers without those silly tricks are a gossip yellow rag, a naval business one, and a "clubs and events" magazine.