A unique display advertisement system was developed at the department of advertising technologies, Yaagl Inc. The system displays advertisements that meet the interests of the user who is currently watching the page.
For this system to function properly, having a good method for computing the user’s category of interest and the probability of clicking an advertisement, which is related to his/her interests, is vital.
One of your colleagues has implemented an algorithm that analyzes users’ browsing history and produces the results as follows:
|
user id |
category id |
create time |
heuristic ctr |
where:
• user id is the user identifier;
• category id is the identifier of user’s predicted interest category;
• create time is the prediction generation time;
• heuristic ctr is the predicted click probability for this category.
This information is stored in interests log table.
Your task is to write a program which estimates the prediction quality. You are provided with log table events log containing advertisement display results. Each row of the table corresponds to advertisement display event. The table has the following columns:
• user id is the user identifier;
• category id is the identifier of an advertisement category;
• adv id is the advertisement identifier;
• show time is the advertisement display time;
• click flag is 1, if a click had occurred, 0 otherwise.
Your are expected to add new information from the first table to the second one, or, as SQL-developers usually say, do an INNER JOIN of these two tables using (user id, category id) as a key.
While performing the join, the following conditions must be satisfied:
• user id and category id of matching rows must be equal;
• each row of the second table can match at most one row of the first table;
• for a pair of matching rows the following must hold — show time > create time and show time − create time is minimum.
All matching rows must appear in the result. However some rows from both tables may not appear in
the result if they have no match.
输入格式
The first line contains the numbers interests count and events count, denoting the sizes of the log tables interests log and events log respectively. The sizes do not exceed 70 000. The next interests count lines contain rows of interests log, and the next events count lines contain rows of the second table. Field values are separated by a space. All field values except for click flag are integers belonging to the range [1, 109]. For the records in interests log, all the tuples (user id, category id, create time) are unique.
输出格式
Output the joined table. Each row should be as follows:
|
user id |
category id |
create time |
heuristic ctr |
adv id |
show time |
click flag |
Print the number of rows in the first line. Then print table rows, one per line. Order the rows by tuples (heuristic ctr, user id, category id, create time, adv id, show time) in the ascending order. Tuples are compared lexicographically, i.e. tuples are compared first by heuristic ctr, then by user id and so on till show time. You can output rows in any order satisfying the described criteria.
样例
Output
1
1 1 102 200 34 105 1
5
3 88 210 1000000 1001 310 0
3 88 210 1000000 1002 211 1
2 88 110 3000000 1005 210 1
2 88 210 4000000 1006 310 0
3 75 100 6000000 1007 331 1