PUCMM331 - SQL Queries

Structured Query Language (SQL) is a special-purpose programming language designed for manipulating relational data. Its most known feature is perhaps the Query, that is, a mechanism by which data can be retrieved based on custom criteria.

The general syntax to construct a SQL Query with filtering criteria is as follows:

     SELECT [list of fields]
     FROM [table]
     WHERE [criteria]

Let us review an example. Consider we have the following table of competitive programmers:

Nickname Country CF_Rating TC_Rating
tourist BY 3205 3693
Petr RU 2676 3738
Egor RU 2732 3463
cjtoribio DO 2019 1381
niquefa_diego CO 2059 1896
Un_Exisstin3 PE 2400 1499

If we wanted to retrieve all competitive programmers who have a CodeForces rating less than 2200 or a TopCoder rating of at most 1500, we could construct the following query:

   SELECT Nickname
   FROM Comp_Programmers
   WHERE CF_Rating < 2200 OR TC_Rating <= 1500

In this example, the query would return nicknames cjtoribio, niquefa_diego and Un_Exisstin3.

We will consider a simplified SQL statement. Assume there is only one table with the same structure as the one provided in the above example. Your program will receive a single criteria with exactly two conditions on the columns CF_Rating and TC_Rating, assembled with either the AND or the OR operator. With this criteria, your program must output the corresponding nicknames of the retrieved rows.

Input

The first line of input contains M (1 <= M <= 50), the number of rows on the table and N (1 <= N <= 20), the number of queries to be performed. The next M lines contain the rows of the table. Each row is completely described in a single line and contains four tokens separated by single space: Nickname, which is a string of length not exceeding 20; Country, an uppercase string of length 2 consisting of letters [A-Z]; CF_Rating, a positive integer in the range [0, 5000] and TC_Rating, similar to CF_Rating. Nicknames are not unique.

The following N lines contain the list of queries to be performed. Each query is described in a single line. The format of a query is as follows (without brackets):

[CF_Rating | TC_Rating] [ < | > | <= | >= ] [positive_integer] [AND | OR] [CF_Rating | TC_Rating] [ < | > | <= | >= ] [positive_integer].

Output

For each query i enumerated from 1 to N:

- output as its first line "Query #i:"

- output each nickname on a separate line

The list of nicknames must be printed in lexicographical order.

Examples

Input
6 2
tourist BY 3205 3693
Petr RU 2676 3738
Egor RU 2732 3463
cjtoribio DO 2019 1381
niquefa_diego CO 2059 1896
Un_Exisstin3 PE 2400 1499
CF_Rating < 2200 OR TC_Rating <= 1500
CF_Rating > 1 AND TC_Rating >= 3600

Output
Query #1:
Un_Exisstin3
cjtoribio
niquefa_diego
Query #2:
Petr
tourist

Added by:Olson Ortiz
Date:2013-01-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Olimpiada de ProgramaciĆ³n PUCMM ACM-ISC 2013

hide comments
2022-07-26 21:48:17 Simes
This is enough fun to be in the classical problem set.
2018-08-02 16:02:22
How do you use SQL to solve the problem?
2014-11-05 14:29:52 Min_25
Pairs of (Nickname, Country) are also not unique.

Last edit: 2014-11-05 15:04:21
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.