There was an emergency at ZZZ Inc.—its secret developments became
known to a competing company! Of course, the primary suspects were the
employees of ZZZ Inc. System administrator Zhuchkov was asked to report who
of the employees had downloaded secret information from the server during the
week preceding the incident. Zhuchkov looked through the logs and found the
personal number and the data access code of the person who had done that. The
administrator gave this information to the company's management, and the same
evening the guilty employee disappeared without a trace and Zhuchkov was given
However, it soon turned out that Zhuchkov had mixed up some symbols both in the
personal number and in the data access code and the sacked employee had in fact
been innocent. To avoid such annoying mistakes in the future, Zhuchkov had
decided to find all the pairs of employees with similar numbers and check how
much their data access codes were similar.
Zhuckov considers two personal numbers similar if one of them can be
obtained from the other by inserting, deleting, or replacing one digit.
Personal numbers do not contain leading zeros. The employees of ZZZ Inc.
are numbered by consecutive integers starting from 1, and their data access codes are lines consisting of
four hexadecimal digits. For each pair of employees with similar personal
numbers, Zhuchkov wants to calculate the number of positions in which their
data access codes differ. Help Zhuchkov.
The first line contains the number n of employees in ZZZ Inc.
(2 ≤ n ≤ 65536). The i-th of the following n lines
contains the data access code of the employee whose personal number is i. The
data access codes consist of digits and lowercase English letters; they are
different for different employees.
Output four space-separated integers. The i-th integer
should be the number of pairs of employees whose personal numbers are similar
and whose data access codes differ in i positions.
0 0 2 1
Problem Author: Daniil Ayzenshteyn
Problem Source: XIV Open USU Championship