Python3----第十四章网络编程

#!usr/bin/env python  
# -*- coding:utf-8 _*-
""" 
@author:AIvision 
@file: lecture14.py 
@time: 2023/09/12 
"""
# 第十四章 网络编程

# 本章首先概述Python标准库中的一些网络模块。然后讨论SocketServer和相关的类，并介绍
# 地介绍同时处理多个连接的各种方法。最后，简单地说一说Twisted，这是一个使用Python编写网
# 络程序的框架，功能丰富而成熟。

# 注意 如果你的计算机上安装了严格的防火墙，每当你开始运行自己编写的网络程序时，它都
# 可能发出警告，并禁止程序连接到网络。你应对防火墙进行配置，让它允许Python完成
# 其工作。如果防火墙有交互式接口，只需在询问时允许建立连接即可。然而，需要注意
# 的是，任何连接到网络的软件都是安全隐患，即便是你自己编写的软件亦如此（或者说
# 尤其如此）。

# 14.1 几个网络模块
# 标准库中有很多网络模块，其他地方也有不少。有些网络模块明显主要是处理网络的，但还
# 有几个其实也是与网络相关的，如处理各种数据编码以便通过网络传输的模块。这里精挑细选了
# 几个模块进行介绍。

# 14.1.1 模块 socket
# 网络编程中的一个基本组件是套接字（socket）。套接字基本上是一个信息通道，两端各有一
# 个程序。这些程序可能位于（通过网络相连的）不同的计算机上，通过套接字向对方发送信息。
# 在Python中，大多数网络编程都隐藏了模块socket的基本工作原理，不与套接字直接交互。
# 套接字分为两类：服务器套接字和客户端套接字。创建服务器套接字后，让它等待连接请求
# 的到来。这样，它将在某个网络地址（由IP地址和端口号组成）处监听，直到客户端套接字建立
# 连接。随后，客户端和服务器就能通信了。
# 客户端套接字处理起来通常比服务器端套接字容易些，因为服务器必须准备随时处理客户端
# 连接，还必须处理多个连接；而客户端只需连接，完成任务后再断开连接即可。本章后面将介绍
# 如何使用SocketServer等类和Twisted框架进行服务器端编程。
# 套接字是模块socket中socket类的实例。实例化套接字时最多可指定三个参数：一个地址族
# （默认为socket.AF_INET）；是流套接字（socket.SOCK_STREAM，默认设置）还是数据报套接字
# （socket.SOCK_DGRAM）；协议（使用默认值0就好）。创建普通套接字时，不用提供任何参数。
# 服务器套接字先调用方法bind，再调用方法listen来监听特定的地址。然后，客户端套接字
# 就可连接到服务器了，办法是调用方法connect并提供调用方法bind时指定的地址（在服务器端，
# 可使用函数socket.gethostname获取当前机器的主机名）。这里的地址是一个格式为(host, port)
# 的元组，其中host是主机名（如www.example.com），而port是端口号（一个整数）。方法listen接
# 受一个参数——待办任务清单的长度（即最多可有多少个连接在队列中等待接纳，到达这个数量
# 后将开始拒绝连接）。
# 服务器套接字开始监听后，就可接受客户端连接了，这是使用方法accept来完成的。这个方
# 法将阻断（等待）到客户端连接到来为止，然后返回一个格式为(client, address)的元组，其中
# client是一个客户端套接字，而address是前面解释过的地址。服务器能以其认为合适的方式处
# 理客户端连接，然后再次调用accept以接着等待新连接到来。这通常是在一个无限循环中完成的。

# 注意 这里讨论的服务器编程形式称为阻断（同步）网络编程。在14.3节，你将看到非阻断（异
# 步）网络编程示例，以及如何使用线程来同时处理多个客户端。

# 为传输数据，套接字提供了两个方法：send和recv（表示receive）。要发送数据，可调用方
# 法send并提供一个字符串；要接收数据，可调用recv并指定最多接收多少个字节的数据。如果不
# 确定该指定什么数字，1024是个不错的选择。
# 代码清单14-1和14-2展示了最简单的客户端程序和服务器程序。如果在同一台机器上运行它们
# （先运行服务器程序），服务器程序将打印一条收到连接请求的消息，然后客户端程序将打印它从服
# 务器那里收到的消息。在服务器还在运行时，可运行多个客户端。在客户端程序中，通过将gethostname
# 调用替换为服务器机器的主机名，可分别在两台通过网络连接的机器上运行这两个程序。

# 代码清单14-1 最简单的服务器
import socket
s = socket.socket()
host = socket.gethostname()
port = 1234
s.bind((host, port))
s.listen(5)
while True:
    c, addr = s.accept()
    print('Got connection from', addr)
    c.send('Thank you for connecting')
    c.close()

# 代码清单14-2 最简单的客户端
import socket
s = socket.socket()
host = socket.gethostname()
port = 1234
s.connect((host,port))
print(s.recv(1024))

# 有关模块socket的更详细信息，请参阅“Python库参考手册”以及Gordon McMillan撰写的文
# 章“Socket Programming HOWTO”（http://docs.python.org/dev/howto/sockets.html）。

# 14.1.2 模块 urllib 和 urllib2
# 在可供使用的网络库中，urllib和urllib2可能是投入产出比最高的两个。它们让你能够通
# 过网络访问文件，就像这些文件位于你的计算机中一样。只需一个简单的函数调用，就几乎可将
# 统一资源定位符（URL）可指向的任何动作作为程序的输入。想想将这种功能与模块re结合起来
# 使用都能做什么吧！你可下载网页、从中提取信息并自动生成研究报告。
# 模块urllib和urllib2的功能差不多，但urllib2更好一些。对于简单的下载，urllib绰绰有
# 余。如果需要实现HTTP身份验证或Cookie，抑或编写扩展来处理自己的协议，urllib2可能是更
# 好的选择。

# 1. 打开远程文件
# 几乎可以像打开本地文件一样打开远程文件，差别是只能使用读取模式，以及使用模块
# urllib.request中的函数urlopen，而不是open（或file）。
# >>> from urllib.request import urlopen
# >>> webpage = urlopen('http://www.python.org')
# 如果连接到了网络，变量webpage将包含一个类似于文件的对象，这个对象与网页http://www.python.org相关联.

# 注意 要在没有联网的情况下尝试使用模块urllib，可使用以file:打头的URL访问本地文件，如
# file:c:\text\somefile.txt（别忘了对反斜杠进行转义）。

# urlopen返回的类似于文件的对象支持方法close、read、readline和readlines，还支持迭代等。
# 假设要提取刚才所打开网页中链接About的相对URL，可使用正则表达式（有关正则表达式
# 的详细信息，请参阅10.3.8节）。
# >>> import re
# >>> text = webpage.read()
# >>> m = re.search(b'about', text, re.IGNORECASE)
# >>> m.group(1)
# '/about/'

# 2. 获取远程文件
# 函数urlopen返回一个类似于文件的对象，可从中读取数据。如果要让urllib替你下载文件，
# 并将其副本存储在一个本地文件中，可使用urlretrieve。这个函数不返回一个类似于文件的对
# 象，而返回一个格式为(filename, headers)的元组，其中filename是本地文件的名称（由urllib
# 自动创建），而headers包含一些有关远程文件的信息（这里不会介绍headers，如果你想更深入地
# 了解它，请在有关urllib的标准库文档中查找urlretrieve）。如果要给下载的副本指定文件名，
# 可通过第二个参数来提供。
# urlretrieve('http://www.python.org', 'C:\\python_webpage.html')
# 这将获取Python官网的主页，并将其存储到文件C:\python_webpage.html中。如果你没有指定
# 文件名，下载的副本将放在某个临时位置，可使用函数open来打开。但使用完毕后，你可能想将
# 其删除，以免占用磁盘空间。要清空这样的临时文件，可调用函数urlcleanup且不提供任何参数，
# 它将负责替你完成清空工作。

# 14.1.3 其他模块
# 前面说过，除了这里讨论的模块外，Python库等地方还包含很多与网络相关的模块。表14-1
# 列出了Python标准库中的一些与网络相关的模块。正如该表指出的，其中有些模块将在本书的其他地方讨论。

# 表14-1 标准库中一些与网络相关的模块
# 模 块                                       描 述
# asynchat                          包含补充asyncore的功能（参见第24章）
# asyncore                          异步套接字处理程序（参见第24章）
# cgi                               基本的CGI支持（参见第15章）
# Cookie                            Cookie对象操作，主要用于服务器
# cookielib                         客户端Cookie支持
# email                             电子邮件（包括MIME）支持
# ftplib                            FTP客户端模块
# gopherlib                         Gopher客户端模块
# httplib                           HTTP 客户端模块
# imaplib                           IMAP4客户端模块
# mailbox                           读取多种邮箱格式
# mailcap                           通过mailcap文件访问MIME配置
# mhlib                             访问MH邮箱
# nntplib                           NNTP客户端模块（参见第23章）
# poplib                            POP客户端模块
# robotparser                       解析Web服务器robot文件
# SimpleXMLRPCServer                一个简单的XML-RPC服务器（参见第27章）
# smtpd                             SMTP服务器模块
# smtplib                           SMTP客户端模块
# telnetlib                         Telnet客户端模块
# urlparse                          用于解读URL
# xmlrpclib                         XML-RPC客户端支持（参见第27章）

# 14.2 SocketServer 及相关的类
# 从14.1.1节可知，编写简单的套接字服务器并不难。然而，如果要创建的并非简单服务器，
# 还是求助于服务器模块吧。模块SocketServer是标准库提供的服务器框架的基石，这个框架包括
# BaseHTTPServer、SimpleHTTPServer、CGIHTTPServer、SimpleXMLRPCServer和DocXMLRPCServer等服
# 务器，它们在基本服务器的基础上添加了各种功能。
# SocketServer包含4个基本的服务器：TCPServer（支持TCP套接字流）、UDPServer（支持UDP
# 数据报套接字）以及更难懂的UnixStreamServer和UnixDatagramServer。后面3个你可能不会用到。
# 使用模块SocketServer编写服务器时，大部分代码都位于请求处理器中。每当服务器收到客
# 户端的连接请求时，都将实例化一个请求处理程序，并对其调用各种处理方法来处理请求。具体
# 调用哪些方法取决于使用的服务器类和请求处理程序类；还可从这些请求处理器类派生出子类，
# 从而让服务器调用一组自定义的处理方法。基本请求处理程序类BaseRequestHandler将所有操作
# 都放在一个方法中——服务器调用的方法handle。这个方法可通过属性self.request来访问客户
# 端套接字。如果处理的是流（使用TCPServer时很可能如此），可使用StreamRequestHandler类，
# 它包含另外两个属性：self.rfile（用于读取）和self.wfile（用于写入）。你可使用这两个类似
# 于文件的对象来与客户端通信。
# 模块SocketServer还包含很多其他的类，它们为HTTP服务器提供基本的支持（如运行CGI
# 脚本），以及XML-RPC支持（这将在第27章讨论）。
# 代码清单14-3是代码清单14-1所示极简服务器的SocketServer版本，可与代码清单14-2所示
# 的客户端协同工作。请注意，StreamRequestHandler负责在使用完连接后将其关闭。另外，主机
# 名''表示运行该服务器的计算机。

# 代码清单14-3 基于SocketServer的极简服务器
from socketserver import TCPServer, StreamRequestHandler
class Handler(StreamRequestHandler):
    def handle(self):
        addr = self.request.getpeername()
        print('Got connection from', addr)
        self.wfile.write('Thank you for connecting')
server = TCPServer(('', 1234), Handler)
server.serve_forever()

# 有关模块SocketServer的详细信息，请参阅“Python库参考手册”以及John Goerzen的著作
# 《Python网络编程基础》。

# 14.3 多个连接
# 前面讨论的服务器解决方案都是同步的：不能同时处理多个客户端的连接请求。如果连接持
# 续的时间较长，比如完整的聊天会话，就需要能够同时处理多个连接。
# 处理多个连接的主要方式有三种：分叉（forking）、线程化和异步I/O。通过结合使用
# SocketServer中的混合类和服务器类，很容易实现分叉和线程化（参见代码清单14-4和14-5）。即
# 便不使用这些类，这两种方式也很容易实现。然而，它们确实存在缺点。分叉占用的资源较多，
# 且在客户端很多时可伸缩性不佳（但只要客户端数量适中，分叉在现代UNIX和Linux系统中的效
# 率很高。如果系统有多个CPU，效率就更高了）；而线程化可能带来同步问题。这里不深入讨论
# 这些问题，只演示如何使用这些方式。

# 14.3.1 使用 SocketServer 实现分叉和线程化
# 使用框架SocketServer创建分叉或线程化服务器非常简单，几乎不需要任何解释。代码清单
# 14-4和14-5分别演示了如何在代码清单14-3所示的服务器中实现分叉和线程化。仅当方法handle
# 需要很长时间才能执行完毕时，分叉和线程化才能提供帮助。请注意，Windows不支持分叉。

# 代码清单14-4 分叉服务器
from socketserver import TCPServer, ForkingMixIn, StreamRequestHandler
class Server(ForkingMixIn, TCPServer): pass
class Handler(StreamRequestHandler):
    def handle(self):
        addr = self.request.getpeername()
        print('Got connection from', addr)
        self.wfile.write('Thank you for connecting')
server = Server(('', 1234), Handler)
server.serve_forever()

# 代码清单14-5 线程化服务器
from socketserver import TCPServer, ThreadingMixIn, StreamRequestHandler
class Server(ThreadingMixIn, TCPServer): pass
class Handler(StreamRequestHandler):
    def handle(self):
        addr = self.request.getpeername()
        print('Got connection from', addr)
        self.wfile.write('Thank you for connecting')
server = Server(('', 1234), Handler)
server.serve_forever()

# 14.3.2 使用 select 和 poll 实现异步 I/O
# 当服务器与客户端通信时，来自客户端的数据可能时断时续。如果使用了分叉和线程化，这
# 就不是问题：因为一个进程（线程）等待数据时，其他进程（线程）可继续处理其客户端。然而，
# 另一种做法是只处理当前正在通信的客户端。你甚至无需不断监听，只需监听后将客户端加入队
# 列即可。
# 这就是框架asyncore/asynchat（参见第24章）和Twisted（参见14.4节）采取的方法。这种功
# 能的基石是函数select或poll（如果系统支持）。这两个函数都位于模块select中，其中poll的可
# 伸缩性更高，但只有UNIX系统支持它（Windows不支持）。

# 函数select接受三个必不可少的参数和一个可选参数，其中前三个参数为序列，而第四个参
# 数为超时时间（单位为秒）。这些序列包含文件描述符整数（也可以是这样的对象：包含返回文
# 件描述符整数的方法fileno），表示我们正在等待的连接。这三个序列分别表示需要输入和输出
# 以及发生异常（错误等）的连接。如果没有指定超时时间，select将阻断（即等待）到有文件描
# 述符准备就绪；如果指定了超时时间，select将最多阻断指定的秒数；如果超时时间为零，select
# 将不断轮询（即不阻断）。select返回三个序列（即一个长度为3的元组），其中每个序列都包含
# 相应参数中处于活动状态的文件描述符。例如，返回的第一个序列包含有数据需要读取的所有输
# 入文件描述符。
# 这些序列也可包含文件对象（Windows不支持）或套接字。代码清单14-6所示的服务器使用
# select来为多个连接提供服务。（请注意，将服务器套接字传递给了select，让select能够在有新
# 连接到来时发出信号。）这个服务器是一个简单的日志程序，将来自客户端的数据都打印出来。
# 要进行测试，可使用telnet连接到它，也可通过编写一个基于套接字的简单客户端来向它发送数
# 据。尝试使用telnet建立多个到该服务器的连接，核实它能够同时处理多个客户端（虽然这样输
# 出的日志中将混杂多个客户端的输入）。

# 代码清单14-6 使用select的简单服务器
import socket, select
s = socket.socket()
host = socket.gethostname()
port = 1234
s.bind((host, port))
s.listen(5)
inputs = [s]
while True:
    rs, ws, es = select.select(inputs, [], [])
    for r in rs:
        if r is s:
            c, addr = s.accept()
            print('Got connection from', addr)
            inputs.append(c)
        else:
            try:
                data = r.recv(1024)
                disconnected = not data
            except socket.error:
                disconnected = True
            if disconnected:
                print(r.getpeername(), 'disconnected')
                inputs.remove(r)
            else:
                print(data)
# 方法poll使用起来比select容易。调用poll时，将返回一个轮询对象。你可使用方法register
# 向这个对象注册文件描述符（或包含方法fileno的对象）。注册后可使用方法unregister将它们删
# 除。注册对象（如套接字）后，可调用其方法poll（它接受一个可选的超时时间参数）。这将返
# 回一个包含(fd, event)元组的列表（可能为空），其中fd为文件描述符，而event是发生的事件。
# event是一个位掩码，这意味着它是一个整数，其各个位对应于不同的事件。各种事件是用select
# 模块中的常量表示的，如表14-2所示。要检查指定的位是否为1（即是否发生了相应的事件），可
# 下面这样使用按位与运算符（&）：
# if event & select.POLLIN: ...

# 表14-2 select模块中的轮询事件常量
# 事 件 名                         描 述
# POLLIN                    文件描述符中有需要读取的数据
# POLLPRI                   文件描述符中有需要读取的紧急数据
# POLLOUT                   文件描述符为写入数据做好了准备
# POLLERR                   文件描述符出现了错误状态
# POLLHUP                   挂起。连接已断开。
# POLLNVAL                  无效请求。连接未打开

# 代码清单14-7使用poll而不是select重写了代码清单14-6所示的服务器。请注意，我添加了
# 一个从文件描述符（int）到套接字对象的映射（fdmap）。

# 代码清单14-7 使用poll的简单服务器

import socket, select
s = socket.socket()
host = socket.gethostname()
port = 1234
s.bind((host, port))
fdmap = {s.fileno(): s}
s.listen(5)
p = select.poll()
p.register(s)
while True:
    events = p.poll()
    for fd, event in events:
        if fd in fdmap:
            c, addr = s.accept()
            print('Got connection from', addr)
            p.register(c)
            fdmap[c.fileno()] = c
        elif event & select.POLLIN:
            data = fdmap[fd].recv(1024)
        if not data: # 没有数据 --连接已关闭
            print(fdmap[fd].getpeername(), 'disconnected')
            p.unregister(fd)
            del fdmap[fd]
        else:
            print(data)

# 有关select和poll的更详细信息，请参阅“Python库参考手册”（http://python.org/doc/lib/
# module-select.html）。另外，阅读标准库模块asyncore和asynchat的源代码（位于安装的Python中
# 的文件asyncore.py和asynchat.py中）也能获得启迪。

# 14.4 Twisted
# Twisted是由Twisted Matrix Laboratories（http://twistedmatrix.com）开发的，这是一个事件驱
# 动的Python网络框架，最初是为编写网络游戏开发的，但现被各种网络软件使用。在Twisted中，
# 你能实现事件处理程序，就像在GUI工具包（参见第12章）中一样。实际上，Twisted与多个常用
# 的GUI工具包（Tk、GTK、Qt和wxWidgets）配合得天衣无缝。
# 本节介绍一些基本概念，并演示如何使用Twisted完成一些简单的网络编程任务。掌握这些基
# 本概念后，你就可参考Twisted文档（可在Twisted网站找到，这个网站还有很多其他的信息）来
# 完成更复杂的网络编程。Twisted是一个功能极其丰富的框架，支持Web服务器和客户端、SSH2、
# SMTP、POP3、IMAP4、AIM、ICQ、IRC、MSN、Jabber、NNTP、DNS等！

# 14.4.1 下载并安装 Twisted
# Twisted安装起来非常容易。首先，访问Twisted Matrix网站（http://twistedmatrix.com），并单
# 击其中的一个下载链接。如果你使用的是Windows，请根据你使用的Python版本下载相应的安装
# 程序。如果你使用的是其他操作系统，请下载源代码归档文件。（如果你使用了包管理器Portage、
# RPM、APT、Fink或MacPorts，可直接下载并安装Twisted。）Windows安装程序是一个循序渐进的
# 向导，不用多解释。编译和解压缩可能需要点时间，但你只需等待就好。要安装源代码归档，
# 首先需要解压缩（先使用tar，再根据下载的归档文件类型使用gunzip或bunzip2），然后运行脚
# 本Distutils。
# python setup.py install
# 这样就应该能够使用Twisted了。

# 14.4.2 编写 Twisted 服务器
# 本章前面编写的简单套接字服务器非常清晰，其中有些包含显式的事件循环，用于查找新连
# 接和新数据。基于SocketServer的服务器有一个隐式的循环，用于查找连接并为每个连接创建处
# 理程序，但处理程序必须显式地读取数据。Twisted（与第24章将讨论的框架asyncore/asynchat
# 一样）采用的是基于事件的方法。要编写简单的服务器，只需实现处理如下情形的事件处理程序：
# 客户端发起连接，有数据到来，客户端断开连接（以及众多其他的事件）。专用类可在基本类的
# 基础上定义更细致的事件，如包装“数据到来”事件，收集换行符之前的所有数据再分派“数据
# 行到来”事件。

# 代码清单14-8 使用Twisted创建的简单服务器
from twisted.internet import reactor
from twisted.internet.protocol import Protocol, Factory
class SimpleLogger(Protocol):
    def connectionMade(self):
        print('Got connection from', self.transport.client)
    def connectionLost(self, reason):
        print(self.transport.client, 'disconnected')

    def dataReceived(self, data):
        print(data)
factory = Factory()
factory.protocol = SimpleLogger
reactor.listenTCP(1234, factory)
reactor.run()

# 代码清单14-9 使用协议LineReceiver改进后的日志服务器
from twisted.internet import reactor
from twisted.internet.protocol import Factory
from twisted.protocols.basic import LineReceiver
class SimpleLogger(LineReceiver):
    def connectionMade(self):
        print('Got connection from', self.transport.client)

        def connectionLost(self, reason):
            print(self.transport.client, 'disconnected')

        def lineReceived(self, line):
            print(line)
factory = Factory()
factory.protocol = SimpleLogger
reactor.listenTCP(1234, factory)
reactor.run()

# 14.5 小结
# 本章简要地介绍了多种Python网络编程方法，选择哪种方法取决于具体需求和你的偏好。选
# 择一种方法后，你很可能需要更深入地学习。下面是本章介绍的一些主题。
#  套接字和模块socket：套接字是让程序（进程）能够通信的信息通道，这种通信可能需要
# 通过网络进行。模块socket让你能够在较低的层面访问客户端套接字和服务器套接字。服
# 务器套接字在指定的地址处监听客户端连接，而客户端套接字直接连接到服务器。
#  urllib和urllib2：这些模块让你能够从各种服务器读取和下载数据，为此你只需提供指
# 向数据源的URL即可。模块urllib是一种比较简单的实现，而urllib2功能强大、可扩展
# 性极强。这两个模块都通过诸如urlopen等函数来完成工作。
#  框架SocketServer：这个框架位于标准库中，包含一系列同步服务器基类，让你能够轻松
# 地编写服务器。它还支持使用CGI的简单Web（HTTP）服务器。如果要同时处理多个连
# 接，必须使用支持分叉或线程化的混合类。
#  select和poll：这两个函数让你能够在一组连接中找出为读取和写入准备就绪的连接。这
# 意味着你能够以循环的方式依次为多个连接提供服务，从而营造出同时处理多个连接的
# 假象。另外，相比于线程化或分叉，虽然使用这两个函数编写的代码要复杂些，但解决
# 方案的可伸缩性和效率要高得多。
#  Twisted：这是Twisted Matrix Laboratories开发的一个框架，功能丰富而复杂，支持大多数
# 主要的网络协议。虽然这个框架很大且其中使用的一些成例看起来宛如天书，但其基本
# 用法简单而直观。框架Twisted也是异步的，因此效率和可伸缩性都非常高。对很多自定
# 义网络应用程序来说，使用Twisted来开发很可能是最佳的选择。

# 14.5.1 本章介绍的新函数
# 函 数                                                               描 述
# urllib.urlopen(url[, data[, proxies]])                    根据指定的URL打开一个类似于文件的对象
# urllib.urlretrieve(url[,fname[,hook[,data]]])             下载URL指定的文件
# urllib.quote(string[, safe])                              替换特殊的URL字符
# urllib.quote_plus(string[, safe])                         与quote一样，但也将空格替换为+
# urllib.unquote(string)                                    与quote相反
# urllib.unquote_plus(string)                               与quote_plus相反
# urllib.urlencode(query[, doseq])                          对映射进行编码，以便用于CGI查询中
# select.select(iseq, oseq, eseq[, timeout])                找出为读/写做好了准备的套接字
# select.poll()                                             创建一个轮询对象，用于轮询套接字
# reactor.listenTCP(port, factory)                          监听连接的Twisted函数
# reactor.run()                                             启动主服务器循环的Twisted函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425