On the distant isle of Googlia, there are two cities, Truthtown and Liarville. People from Truthtown always tell the truth and people from Liarville always lie. While exploring Googlia, you have run across a group of N inhabitants, and you want to figure out which city each one came from.

To make life simpler, you begin by numbering these people 1 through N. You then question each person, and record their M statements in the short-hand described below.