CF107C.Arrangement

In the year 2500 the annual graduation ceremony in the German University in Cairo (GUC) has run smoothly for almost 500 years so far.

The most important part of the ceremony is related to the arrangement of the professors in the ceremonial hall.

Traditionally GUC has n professors. Each professor has his seniority level. All seniorities are different. Let's enumerate the professors from 1 to n, with 1 being the most senior professor and n being the most junior professor.

The ceremonial hall has n seats, one seat for each professor. Some places in this hall are meant for more senior professors than the others. More specifically, m pairs of seats are in "senior-junior" relation, and the tradition requires that for all m pairs of seats (a__i, b__i) the professor seated in "senior" position a__i should be more senior than the professor seated in "junior" position b__i.

GUC is very strict about its traditions, which have been carefully observed starting from year 2001. The tradition requires that:

• The seating of the professors changes every year.
• Year 2001 ceremony was using lexicographically first arrangement of professors in the ceremonial hall.
• Each consecutive year lexicographically next arrangement of the professors is used.

The arrangement of the professors is the list of n integers, where the first integer is the seniority of the professor seated in position number one, the second integer is the seniority of the professor seated in position number two, etc.

Given n, the number of professors, y, the current year and m pairs of restrictions, output the arrangement of the professors for this year.

公元2500年，开罗德国大学（GUC）的年度毕业典礼已顺利举行了近500年。

典礼中最重要的环节，是礼堂内教授们的就座安排。

按照传统，GUC共有 $n$ 位教授。每位教授具有唯一的资历等级（seniority level）。我们将教授编号为 $1$ 至 $n$，其中编号 $1$ 表示资历最深的教授，编号 $n$ 表示资历最浅的教授。

礼堂中共有 $n$ 个座位，每位教授一个座位。礼堂中某些座位被规定为“资历较深”座位，其余则相对“资历较浅”。更具体地说，存在 $m$ 对座位，构成“资深—资浅”关系；依照传统，对每一对这样的座位 $(a_i,\,b_i)$，坐在“资深”位置 $a_i$ 上的教授，其资历必须高于坐在“资浅”位置 $b_i$ 上的教授。

GUC 对其传统极为严格，自2001年起便一丝不苟地遵循这些规定。该传统要求：

• 教授的就座安排每年必须不同；
• 2001年毕业典礼采用的是礼堂座位安排中字典序最小的合法排列；
• 此后每一年均采用字典序上紧邻的下一个合法排列。

教授的就座安排表示为一个长度为 $n$ 的整数序列：序列中第一个整数表示坐在第1号座位上的教授的资历等级，第二个整数表示坐在第2号座位上的教授的资历等级，依此类推。

给定教授人数 $n$、当前年份 $y$，以及 $m$ 对限制条件（即 $m$ 对“资深—资浅”座位），请输出该年份所对应的教授就座安排。

The first line contains three integers n, y and m (1 ≤ n ≤ 16, 2001 ≤ y ≤ 1018, 0 ≤ m ≤ 100) — the number of professors, the year for which the arrangement should be computed, and the number of pairs of seats for which the seniority relation should be kept, respectively.

The next m lines contain one pair of integers each, "a__i b__i", indicating that professor on the a__i-th seat is more senior than professor on the b__i-th seat (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i). Some pair may be listed more than once.

Please, do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin stream (you may also use the %I64d specificator).

第一行包含三个整数 $n$、$y$ 和 $m$（$1 ≤ n ≤ 16$，$2001 ≤ y ≤ 10^{18}$，$0 ≤ m ≤ 100$），分别表示教授人数、需计算座位安排的年份，以及需保持资历顺序的座位对数量。

接下来的 $m$ 行每行包含一对整数 $a_i\ b_i$，表示坐在第 $a_i$ 个座位上的教授比坐在第 $b_i$ 个座位上的教授资历更老（$1 ≤ a_i,\,b_i ≤ n$，且 $a_i ≠ b_i$）。某些座位对可能被重复列出。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 格式说明符。推荐使用 cin 流（也可使用 %I64d 格式说明符）。

Print the order in which the professors should be seated in the requested year.

If by this year the GUC would have ran out of arrangements, or the given "senior-junior" relation are contradictory, print "The times have changed" (without quotes).

按要求的年份，输出教授们应就座的顺序。

如果到该年份开罗德国大学（GUC）已用尽所有可能的排列方式，或给定的“资深-资浅”关系存在矛盾，则输出 “The times have changed”（不带引号）。

In the first example the lexicographically first order of seating is 1 2 3.

In the third example the GUC will run out of arrangements after the year 3630800.

In the fourth example there are no valid arrangements for the seating.

The lexicographical comparison of arrangements is performed by the < operator in modern programming languages. The arrangement a is lexicographically less that the arrangement b, if there exists such i (1 ≤ i ≤ n), that a__i < b__i, and for any j (1 ≤ j < i) a__j = b__j.

在第一个例子中，字典序最小的就座顺序为 1 2 3。

在第三个例子中，GUC 将在 3630800 年后耗尽所有可能的排列方案。

在第四个例子中，不存在满足条件的就座方案。

排列之间的字典序比较由现代编程语言中的 < 运算符执行。若存在某个下标 $i$（$1 ≤ i ≤ n$），使得 $a_i < b_i$，且对任意 $j$（$1 ≤ j < i$）均有 $a_j = b_j$，则称排列 $a$ 的字典序小于排列 $b$。