Seol mar théacs é seo: The complexity of maximal constraint languages